Cost-aware Generalized $\alpha$-investing for Multiple Hypothesis Testing

Thomas Cook Dept. of Mathematics & Statistics University of Massachusetts
Amherst, MA 01002<EMAIL_ADDRESS>Harsh Vardhan Dubey Dept. of Mathematics &
Statistics University of Massachusetts Amherst, MA 01002<EMAIL_ADDRESS>Ji
Ah Lee Dept. of Mathematics & Statistics University of Massachusetts Amherst,
MA 01002<EMAIL_ADDRESS>
Guangyu Zhu Dept. of Statistics University of Rhode Island Kingston, RI 02881
<EMAIL_ADDRESS>Tingting Zhao††thanks: co-corresponding author Dept. of
Information Systems & Analytics Bryant University Smithfield, RI 02917
<EMAIL_ADDRESS>Patrick Flaherty††footnotemark:  Dept. of Mathematics &
Statistics University of Massachusetts Amherst, MA 01002<EMAIL_ADDRESS>
###### Abstract

We consider the problem of sequential multiple hypothesis testing with
nontrivial data collection cost. This problem appears, for example, when
conducting biological experiments to identify differentially expressed genes
in a disease process. This work builds on the generalized $\alpha$-investing
framework that enables control of the false discovery rate in a sequential
testing setting. We make a theoretical analysis of the long term asymptotic
behavior of $\alpha$-wealth which motivates a consideration of sample size in
the $\alpha$-investing decision rule. Posing the testing process as a game
with nature, we construct a decision rule that optimizes the expected return
(ERO) of $\alpha$-wealth and provides an optimal sample size for the test.
Empirical results show that a cost-aware ERO decision rule correctly rejects
more false null hypotheses than other methods. We extend cost-aware ERO
investing to finite-horizon testing which enables the decision rule to
allocate samples across many tests. Finally, empirical tests on real data sets
from biological experiments show that cost-aware ERO produces actionable
decisions to conduct tests at optimal sample sizes.

##  1 INTRODUCTION

Machine learning systems are increasingly used to make decisions in uncertain
environments. Decision-making can be viewed in the framework of hypothesis
testing in that a decision is made as the result of a rejection of the null
hypothesis (Arrow et al.,, 1949; Dickey and Lientz,, 1970; Blackwell and
Girshick,, 1979; Verdinelli and Wasserman,, 1995; Parmigiani and Inoue,, 2009;
Berger,, 2013). When multiple hypotheses are under consideration, a false
discovery rate (FDR) control procedure provides a way to control the rate of
erroneous rejections in a batch of hypotheses for small-scale data sets
(Benjamini and Hochberg,, 1995; Storey,, 2002; Storey et al.,, 2004; Benjamini
et al.,, 2006; Zeisel et al.,, 2011; Liang and Nettleton,, 2012). However,
these procedures typically require the test statistics of all of the
hypotheses under consideration so that the p-values may be sorted and a set of
hypotheses may be selected for rejection. In many modern problems the test
statistics for all the hypotheses may not be known simultaneously and standard
FDR procedures do not work.

Online FDR methods have recently been developed to address the need for FDR
control procedures that maintain control for a sequence of tests when the test
statistics are not all known at one time. Tukey and Braun, (1994) proposed the
idea that one starts with a fixed amount “$\alpha$-wealth” and for each
hypothesis under consideration, the researcher may choose to spend some of
that wealth until it is all gone. Foster and Stine, (2008) extended
$\alpha$-spending by allowing some return on the expenditure of
$\alpha$-wealth if the hypothesis is successfully rejected. Aharoni and
Rosset, (2014) introduced generalized $\alpha$-investing and provided a
deterministic decision rule to optimally set the $\alpha$-level for each test
given the history of test outcomes. A full review of related work is in
Section 1.2.

###  1.1 Contributions

We extend generalized $\alpha$-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 $\alpha$-wealth
in an $\alpha$-investing procedure,

  * •

a generalized $\alpha$-investing procedure for sequential testing that
simultaneously optimizes sample size and $\alpha$-level using game-theoretic
principles,

  * •

a non-myopic $\alpha$-investing procedure that maximizes the expected reward
over a finite horizon of tests.

###  1.2 Related Work

Tukey proposed the notion of $\alpha$-wealth to control the family-wise error
rate for a sequence of tests (Tukey,, 1991; Tukey and Braun,, 1994). Foster
and Stine, (2008) proposed $\alpha$-investing, an online procedure that
controls the marginal FDR (mFDR) for any stopping time in the testing
sequence. Aharoni and Rosset, (2014) introduced generalized $\alpha$-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 (Yang et al.,, 2017; Ramdas et al.,, 2019).
Javanmard and Montanari, (2018) first proved that generalized
$\alpha$-investing controls FDR, not only mFDR under an online setting with an
algorithm called LORD. Ramdas et al., (2017) 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 (Xia et al.,,
2017) and online (Chen and Kasiviswanathan,, 2020). Ramdas et al., (2018) then
proposed SAFFRON, which also belongs to the $\alpha$-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 et al., (2021) extend $\alpha$-investing
methods to an asynchronous setting where tests are allowed to overlap in time.
These state-of-the-art online FDR control $\alpha$-investing methods do not
address the needs for testing when the cost of data is not negligible. So, we
propose a novel $\alpha$-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 $\alpha$-investing. Section
3 contains a theoretical analysis of the long term asymptotic behavior of the
$\alpha$-wealth. Section 4 presents a cost-aware generalized
$\alpha$-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 $\alpha$-investing aligns with
the overall objectives of the application setting. Finally, Section 7
describes limitations and future work.

##  2 BACKGROUND ON GENERALIZED $\alpha$-INVESTING

Following the notation of Foster and Stine, (2008), consider $m$ null
hypotheses, $H_{1},\ldots,H_{m}$ where $H_{j}\subset\Theta_{j}$. The random
variable $R_{j}\in\\{0,1\\}$ is an indicator of whether $H_{j}$ is rejected
regardless of whether the null is true or not. The random variable
$V_{j}\in\\{0,1\\}$ indicates whether the test $H_{j}$ is both true and
rejected. These variables are aggregated as $R(m)=\sum_{j=1}^{m}R_{j}$ and
$V(m)=\sum_{j=1}^{m}V_{j}$. With these definitions, the FDR (Benjamini and
Hochberg,, 1995) is

$\text{FDR}(m)=P_{\theta}(R(m)>0)\
\mathbb{E}_{\theta}\left[\frac{V(m)}{R(m)}\mid R(m)>0\right],$

and the marginal false discovery rate (mFDR) is

$\text{mFDR}_{\eta}(m)=\frac{\mathbb{E}_{\theta}\left[V(m)\right]}{\mathbb{E}_{\theta}\left[R(m)+\eta\right]}.$

Setting $\eta=1-\alpha$ provides weak control over the family-wise error rate
at level $\alpha$.

Aharoni and Rosset, (2014) make two assumptions in their development of
generalized $\alpha$-investing:

$\displaystyle\forall\theta_{j}\in
H_{j}:P_{\theta_{j}}(R_{j}|R_{j-1},\ldots,R_{1})$ $\displaystyle\leq$
$\displaystyle\alpha_{j},$ (1) $\displaystyle\forall\theta_{j}\not\in
H_{j}:P_{\theta_{j}}(R_{j}|R_{j-1},\ldots,R_{1})$ $\displaystyle\leq$
$\displaystyle\rho_{j},$ (2)

where

$\rho_{j}=\sup_{\theta_{j}\in\Theta_{j}-H_{j}}P_{\theta_{j}}(R_{j}=1).$ (3)

Assumption 1 constrains the false positive rate to the level of the test and
Assumption 2 is an upper bound of $\rho_{j}$ on the power of the test. A pool
of $\alpha$-wealth, $W_{\alpha}(j)$, is available to spend on the $j$-th
hypothesis. The $\alpha$-wealth is updated according to the following
equations:

$\displaystyle W_{\alpha}(0)$ $\displaystyle=$ $\displaystyle\alpha\eta,$ (4)
$\displaystyle W_{\alpha}(j)$ $\displaystyle=$ $\displaystyle
W_{\alpha}(j-1)-\varphi_{j}+R_{j}\psi_{j}.$ (5)

A deterministic function $\mathcal{I}_{W_{\alpha}(0)}$ is an
$\alpha$-investing rule that determines: the cost of conducting the $j$-th
hypothesis test, $\varphi_{j}$; the reward for a successful rejection,
$\psi_{j}$; and the level of the test, $\alpha_{j}$:

$(\varphi_{j},\alpha_{j},\psi_{j})=\mathcal{I}_{W_{\alpha}(0)}(\\{R_{1},\ldots,R_{j-1}\\}).$
(6)

The $\alpha$-investing rule depends only on the outcomes of the previous
hypothesis tests. The Foster-Stine cost depends hyperbolically on the level of
the test $\varphi_{j}=\alpha_{j}/(1-\alpha_{j})$.

Generalized $\alpha$-investing can be viewed in a game-theoretic framework
where the outcome of the test (reject or fail-to-reject) is random and the
procedure provides the optimal amount of “ante” to offer to play and “payoff”
to demand should the test successfully reject. We make use of this game
theoretic interpretation in our contributions in Section 4.1.

Aharoni and Rosset, (2014) derive a linear constraint on the reward $\psi_{j}$
to ensure that, for a given $(\varphi_{j},\alpha_{j})$, the mFDR is controlled
at a level $\alpha$ by ensuring the sequence $A(j)=\alpha
R_{j}-V_{j}+\alpha\eta-W_{\alpha}(j)$ is a submartingale with respect to
$R_{j}$. That constraint is

$\psi_{j}\leq\min\left(\frac{\varphi_{j}}{\rho_{j}}+\alpha,\frac{\varphi_{j}}{\alpha_{j}}+\alpha-1\right).$
(7)

Maximizing the expected reward of the next hypothesis test,
$\mathbb{E}(R_{j})\psi_{j}$, leads to the following equality

$\frac{\varphi_{j}}{\rho_{j}}=\frac{\varphi_{j}}{\alpha_{j}}-1.$ (8)

Note that this equality selects the point of intersection of the two parts of
the constraint in (7). Expected Reward Optimum (ERO) $\alpha$-investing
provides two equations for three unknowns in the deterministic decision rule.
Aharoni and Rosset, (2014) address this indeterminacy by considering three
allocation schemes for $\varphi_{j}$: constant, relative, and relative200 and
suggest that the investigator can explore various options and set
$\varphi_{j}$ on their own. Further details on these schemes are given in
Section 5.

Since the dominant paradigm in testing of biological hypotheses is a bounded
finite range for $\Theta_{j}$, for the remainder we assume
$\Theta_{j}=[0,\bar{\theta}_{j}]$ for some upper bound, $\bar{\theta}_{j}$,
and $H_{j}=\\{0\\}$. This scenario may be viewed as a test that the expression
for gene $j$ is differentially increased in an experimental condition compared
to a control. We consider a simple z-test here for concreteness. The power of
a one-sided z-test is
$(1-\beta):=1-\Phi\left(z_{1-\alpha}+\frac{(\mu_{0}-\mu_{1})}{\sigma/\sqrt{n}}\right)$
where $z_{1-\alpha}=\Phi^{-1}(1-\alpha)$ is the z-score corresponding to level
$\alpha$, $\mu_{0}$ is the expected value of the simple null hypothesis,
$\mu_{1}$ is the expected value of the simple alternative hypothesis, $\sigma$
is the standard deviation of the measurements, and $n$ is the sample size.

Using Equation (3), the best power under the previously defined $\Theta_{j}$
is

$\rho_{j}=1-\Phi\left(z_{1-\alpha_{j}}-\frac{\bar{\theta}_{j}}{\sigma_{j}/\sqrt{n_{j}}}\right).$
(9)

The best power depends on: (1) the level of the test, $\alpha_{j}$, (2) the
scale of the bound on the alternative, $\bar{\theta}_{j}$, (3) the sample
size, $n_{j}$, and the measurement standard deviation, $\sigma_{j}$. One may
compare multiple measurement technologies based on their precision by
exploring the effect of changing $\sigma_{j}$ — for example, for a fixed
budget and all other things equal, a trade-off can be computed between more
samples with a higher variance technology, versus fewer samples with a lower
variance technology. For the remainder, we assume $\sigma_{j}$ is fixed and
known. ERO $\alpha$-investing for Neyman-Pearson testing problems is solved by
the following nonlinear optimization problem: |s| α_j, ψ_j E_θ (R_j) ψ_j
ψ_j≤φjρj \+ α ψ_j≤φjαj \+ α\- 1 φjρj= φjαj \- 1 ρ_j= 1 - Φ( z_1-α_j - ¯θjσj/
nj ) Constraints 2 and 9 correspond to (7) which controls the mFDR level, and
constraint (9) ensures the maximal expected reward for the $j$-th test. The
optimal ERO solution still depends on an external choice of the sample size
$n_{j}$, and the cost of the test $\varphi_{j}$.

##  3 LONG-TERM $\alpha$-WEALTH

Since the levels of future tests depend on the amount of $\alpha$-wealth
available at the time of the tests, a theoretical consideration in generalized
$\alpha$-investing is whether the long-term $\alpha$-wealth is submartingale
or supermartingale (stochastically non-decreasing or stochastically non-
increasing) for a given decision-rule. Most prior works include some implicit
consideration of the behavior of the long-term $\alpha$-wealth. In zhou, which
predates the seminal work of Foster and Stine, (2008), test levels are set
such that testing may continue indefinitely, even in the worst case scenario
of no rejections, while still utilizing all initial $\alpha$-wealth. Foster
and Stine, (2008) discuss strategies for setting the level of the test and
provide some examples designed to accumulate $\alpha$-wealth for future tests.
They also discuss the practical and ethical concerns with sorting easily
rejected tests so as to accumulate an arbitrary amount of $\alpha$-wealth
before conducting more uncertain tests. Aharoni and Rosset, (2014) seek to
optimize the expected reward of the current test in an effort to maximize the
$\alpha$-wealth available, and, in-turn, the levels for future tests.
Javanmard and Montanari, (2018) discuss setting the vector $\gamma$ such that
the power is maximimized for a mixture model set a-priori for the hypothesis
stream. In all of these methods, the motivation is to have sufficient
$\alpha$-wealth to conduct tests,with an appreciable power perpetually. Here
we outline two scenarios where the long-term $\alpha$-wealth can be either
submartingale or supermartingale.

In order to state the theorems regarding the $\alpha$-wealth sequence, we
require a lemma bounding $\alpha$-wealth as a function of the prior
probability of the null hypothesis.

######  Lemma 1.

Given an $\alpha_{j}$-level for the $j$-th hypothesis test from rule
$\mathcal{I}(R_{1},\ldots R_{j-1})$, the expected value of $\alpha$-wealth for
Foster-Stine $\alpha$-investing is

$\begin{split}\mathbb{E}^{j-1}\left[W_{j}\right]&\leq\\\
-\frac{\alpha_{j}}{1-\alpha_{j}}&+\left[\rho_{j}-(\rho_{j}-\alpha_{j})q_{j}\right]\left(\alpha+\frac{\alpha_{j}}{1-\alpha_{j}}\right),\end{split}$
(10)

where
$\mathbb{E}^{j-1}\left[W_{j}\right]=\mathbb{E}\left[W(j)-W(j-1)|W(j-1)\right]$,
and $q_{j}=\Pr[\theta_{j}\in H_{j}]$, the prior probability (belief) that the
$j$-th null hypothesis is true. In the case of a simple null and alternative
$\Theta_{j}=\\{0,\bar{\theta}_{j}\\}$, the bound is tight.

###### Proof.

Proof is provided in Appendix A. ∎

We are now in a position to understand dynamical properties of the expected
value of the sequence of $\alpha$-wealth, $\\{W(j):j\in\mathbb{N}\\}$.

######  Theorem 1 (Submartingale $\alpha$-Wealth).

Given a simple null and alternative $\Theta_{j}=\\{0,\bar{\theta}_{j}\\}$,
$\\{W(j):j\in\mathbb{N}\\}$ is submartingale (stochastically non-decreasing)
with respect to $\\{R_{1},\dots,R_{j-1}\\}$ if

$\rho_{j}\geq\frac{\alpha_{j}/(1-\alpha_{j})}{\alpha+\alpha_{j}/(1-\alpha_{j})}\frac{1}{1-q_{j}}.$
(11)

###### Proof.

Proof is provided in Appendix A. ∎

Theorem 1 shows that one will be able to conduct an infinite number of tests
in the long-term if the power is close to one or the prior probability of the
null is close to zero. This scenario may occur when the hypothesis stream
contains a large proportion of true alternative hypotheses, or if the sample
sizes of the individual tests are large.

######  Theorem 2 (Supermartingale $\alpha$-Wealth).

For any null and alternative hypothesis, $\\{W(j):j\in\mathbb{N}\\}$ is
supermartingale (stochastically non-increasing) with respect to
$\\{R_{1},\dots,R_{j-1}\\}$ if

$\rho_{j}\leq\left(\frac{\alpha_{j}/(1-\alpha_{j})}{\alpha+\alpha_{j}/(1-\alpha_{j})}-q_{j}\right)\frac{1}{1-q_{j}}.$
(12)

###### Proof.

Proof is provided in Appendix A. ∎

Theorem 2 shows that the generalized $\alpha$-investing testing procedure will
end in a finite number of steps if the power of the test is close to zero or
the prior probability of the null hypothesis is close to one. This scenario
may occur when the hypothesis stream is made up of a large proportion of true
null hypotheses, or if the sample sizes used for each test results in an under
powered test.

These theorems provide general insights for understanding when the
$\alpha$-wealth can be expected to be (stochastically) non-decreasing or non-
increasing. The non-decreasing sequences require that $\rho_{j}\uparrow 1$ for
a fixed $\bar{\theta}_{j}$ which, in the case of a Gaussian, would require
$\sigma_{j}/\sqrt{n}\rightarrow 0$ or $n\rightarrow\infty$. So, the
$\alpha$-wealth grows unbounded if the sample size is unbounded. This theory
in combination with the premise of non-trivial experiment costs motivates the
need for methods for cost-aware $\alpha$-investing when the sample size is not
fixed.

##  4 COST-AWARE GENERALIZED $\alpha$-INVESTING

Our development in this section derives from two key differences in
assumptions compared to previous work. Here we make the following assumptions:
(1) the per sample monetary cost to conduct hypothesis tests is not trivial,
and (2) the $\alpha$-cost of a hypothesis test, $\varphi_{j}$, should account
for the a-priori probability that the null hypothesis is true as well as the
pattern of previous rejections.

###  4.1 Cost-aware ERO $\alpha$-investing

The generalized $\alpha$-investing decision rule, (6), is augmented to include
a notion of dollar-wealth $W_{\$}(j)$ available for expenditure to collect
data to test the $j$-th hypothesis

$(\varphi_{j},\alpha_{j},\psi_{j},n_{j})=\mathcal{I}(W_{\alpha}(0),W_{\$}(0))(\\{R_{1},\ldots,R_{j-1}\\}),$
(13)

where $n_{j}$ is the sample size allocated for testing of the $j$-th
hypothesis. A natural update plan for the dollar-wealth is

$\displaystyle W_{\$}(0)$ $\displaystyle=$ $\displaystyle B$ (14)
$\displaystyle W_{\$}(j)$ $\displaystyle=$ $\displaystyle
W_{\$}(j-1)-c_{j}n_{j},$ (15)

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. The augmented optimization problem
is identical to Problem 9 with objective
$\max_{\varphi_{j},\alpha_{j},\psi_{j},n_{j}}\mathbb{E}_{\theta}(R_{j})\psi_{j}$
and constraint $n_{j}c_{j}\leq W_{\$}(j)$.

###  4.2 Game Theoretic Formulation

The resulting optimization problem has an infinite number of solutions because
$\varphi_{j}$ is not constrained. Thus the problem does not yet constitute a
self-contained decision rule for (13). Indeed, Aharoni and Rosset, (2014),
throughout, suggest a scenario where $\varphi_{j}$ is chosen by the
investigator and the level and reward are given by the decision rule. In such
a scenario, $\varphi_{j}$ can be interpreted as ante for a game against
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 $\theta_{j}\in H_{j}$ with probability $q_{j}$ and
$\theta_{j}\not\in H_{j}$ otherwise. The utility function for this game is the
change in $\alpha$-wealth. The payoff matrix for the game is provided in Table
1.

| Player II (Nature)
---|---
|  | $\theta_{j}\in H_{j}$ | $\theta_{j}\not\in H_{j}$
Player I | Conduct Test | $-\varphi_{j}+\alpha_{j}\psi_{j}$ | $-\varphi_{j}+\rho_{j}\psi_{j}$
(investigator) | Skip Test | 0 | 0

Table 1: Payoff matrix for posing hypothesis testing as a game against nature.
The payouts shown are the expected value of the payout for a given pair of
pure strategies.

If the investigator chooses not to conduct the test, there is no cost
($\varphi_{j}=0$) and there is no reward ($\psi_{j}=0$) regardless of what
nature has chosen. So, the change in $\alpha$-wealth when not conducting a
test is zero. If the investigator chooses to conduct a test, and nature has
hidden $\theta_{j}\in H_{j}$, then the payout is $-\varphi_{j}$ with
probability $1-\alpha_{j}$, or $-\varphi_{j}+\psi_{j}$ with probability
$\alpha_{j}$. In expectation, this payout is
$-\varphi_{j}+\alpha_{j}\psi_{j}$. Similarly, if the investigator chooses to
conduct the test and nature has hidden $\theta_{j}\not\in H_{j}$, then the
expected payout is $-\varphi_{j}+\rho_{j}\psi_{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
$\alpha$-wealth is identical for both of the investigator’s strategies. By
designing the payoff matrix, given 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.

Such a payoff matrix is a solution to the equation,

$q_{j}(-\varphi_{j}+\alpha_{j}\psi_{j})+(1-q_{j})(-\varphi_{j}+\rho_{j}\psi_{j})=0.$

Since the expected payoff for not testing is 0, this equation ensures that the
expected change in $\alpha$-wealth when testing is also 0. By definition, this
gives a self contained decision rule that makes $\alpha$-wealth martingale,
striking a balance between the two scenarios given in Theorem 1 and Theorem 2.

######  Theorem 3 (Martingale $\alpha$-Wealth).

Given a simple null and alternative $\Theta_{j}=\\{0,\bar{\theta}_{j}\\}$,
$\\{W(j):j\in\mathbb{N}\\}$ is martingale with respect to
$\\{R_{1},\dots,R_{j-1}\\}$ if

$\rho_{j}=\left(\frac{1}{1-q_{j}}\right)\left(\frac{\varphi_{j}}{\psi_{j}}-q_{j}\alpha_{j}\right).$
(16)

###### Proof.

Proof is provided in Appendix A. ∎

Theorem 3 provides a condition on the power of the test which requires a
balance between the ratio of $\varphi_{j}$ and $\psi_{j}$ and the probability
of a false positive. _Next, we present our main result, a self-contained
decision rule to provide a martingale $\alpha$-wealth sequence._

###  4.3 Cost-aware ERO Decision Rule

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. In the long-run the best strategy for the investigator
is to ensure that the $\alpha$-wealth sequence is martingale. Incorporating
this objective and the cost of the experiment into the ERO problem yields a
self-contained decision rule in the form of (13), |s| φ_j, α_j, ψ_j, n_j
E_θ(R_j)ψ_j ψ_j≤φjρj \+ α ψ_j≤φjαj \+ α\- 1 φjρj= φjαj \- 1 ρ_j= 1 - Φ(
z_1-α_j - ¯θjσj/ nj ) φ_j≤a * W_α(j-1) n_j c_j≤W_$(j) 0= E[ΔW_α],

Constraints (4.3) and (4.3) ensure control over the mFDR. Constraint (4.3)
connects the level, power, and sample size of the test. Constraints (4.3) and
(4.3) ensure the existing $(\alpha,\$)$-wealth is not exceeded. The parameter
$a\in(0,1]$ controls the proportion of $\alpha$-wealth that a single test can
be allocated. Constraint (4.3) ensures nature’s strategy is equalizing.
Written out explicitly,

$\mathbb{E}\left[\Delta
W_{\alpha}\right]=(-\varphi_{j}+\psi_{j})\Pr[R_{j}=1]+(-\varphi_{j})\Pr[R_{j}=0],$
$\Pr[R_{j}=1]=\alpha_{j}q_{j}+\rho_{j}(1-q_{j}),$
$\Pr[R_{j}=0]=(1-\alpha_{j})q_{j}+(1-\rho_{j})(1-q_{j}).$

A pseudo-code algorithm of the full cost-aware ERO method and further
extensions to cost-aware ERO are described in Appendix C.

######  Lemma 2.

The cost-aware ERO decision rule ensures that $\alpha$-wealth,
$W_{\alpha}(j)$, is martingale with respect to $\\{R_{1},\dots,R_{j-1}\\}$.

###### Proof.

Constraint (4.3) sets $\alpha$-wealth to be martingale by definition. ∎

Constraint (4.3) sets the expected change in $\alpha$-wealth equal to zero.
This enforces that $W_{\alpha}(j)$ is martingale. Allowing $W_{\alpha}(j)$ to
be submartingale, as per Theorem 1, can lead to a situation where hypotheses
are tested at high $\alpha$-levels due to the accumulated $W_{\alpha}$ from
previous rejections. This is referred to as piggybacking in the literature
when such accumulated wealth leads to poor decisions (Ramdas et al.,, 2017).
On the other hand, allowing $W_{\alpha}(j)$ to be supermartingale, as per
Theorem 2, causes the testing to end, and is referred to as $\alpha$-death in
the literature. Using a game-theoretic formulation allows us to propose an
expected-reward optimal procedure which considers preventing $\alpha$-death
and piggy-backing.

Figure 1: Extensive form of two-step game between Investigator (Player I) and
the Nature (Player II). Strategies for each player are italicized. The leaves
are labeled to denote the strategy taken by the investigator and are
enumerated for equations presented in Appendix G.

Constraint (4.3) only controls the _expected_ increment in $W_{\alpha}$. It is
well known that martingale-based strategies can suffer from what is known as
_gambler’s ruin_. Since no bounds are set on the worst case scenario, which in
this case is when $R_{j}=0$, it is possible that we could set
$\varphi_{j}=W_{\alpha}(j-1)$, and suffer $\alpha$-death. This occurs, for
example, when $q_{j}$ is close to $0$, and $\mu_{A}$ and $\sigma_{j}$ allow
for $\rho_{j}\to 1$. In such a case, a rejection is almost certain, and in
turn, so is receiving the reward $\psi_{j}$. Recall that we restrict ourselves
to an ERO solution, and thus, we can interpret constraint (4.3), without the
factor $a$, as setting $\varphi_{j}$ to the expected reward - the quantity
that we are maximizing. In order to keep $W_{\alpha}$ martingale, this almost
guaranteed upside must be counteracted by a devastating downside. In order to
avoid $\alpha$-death, we add a factor which limits the maximal bet. Following
the relative scheme chosen in (Aharoni and Rosset,, 2014), we set this factor
to be $0.1$.

###  4.4 Finite horizon cost-aware ERO $\alpha$-investing

The standard ERO framework optimizes only the one-step expected return,
$\mathbb{E}_{\theta}(R_{j})\psi_{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
$\theta_{j}$ in the null or alternative hypothesis region, and the
investigator, who seeks to find $\theta_{j}$ and gain the reward for doing so,
is shown in Figure 1. 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 $(\alpha,\$)$-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

$\displaystyle\mathbb{E}(R_{j}\psi_{j}$
$\displaystyle+R_{j+1}\psi_{j+1})=\mathbb{E}(R_{j})\psi_{j}+$ (17)
$\displaystyle\psi_{j+1}[P(R_{j}=0)\mathbb{E}(R_{j+1}|R_{j}=0)+$
$\displaystyle P(R_{j}=1)\mathbb{E}(R_{j+1}|R_{j}=1)]$

with constraints (4.3)-(4.3) from Problem 4.3 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.3 when $W_{\$}>>0$. This holds
since the parameters of the second test depend on the expected $\alpha$-wealth
available at that step. When the expected increment is $0$, as set in
constraint (4.3), 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.

##  5 SYNTHETIC DATA EXPERIMENTS

|  | Tests | True Rejects | False Rejects | mFDR
---|---|---|---|---|---
Scheme | Method |  |  |  |
constant |  $\alpha$-spending | 10.0 | 0.28 | 0.04 | 0.032
|  $\alpha$-investing | 16.0 | 0.44 | 0.06 | 0.044
|  $\alpha$-rewards $k=1$ | 14.7 | 0.41 | 0.06 | 0.043
|  $\alpha$-rewards $k=1.1$ | 16.4 | 0.44 | 0.06 | 0.043
| ERO investing | 18.3 | 0.50 | 0.07 | 0.048
relative |  $\alpha$-spending | 66.0 | 0.55 | 0.04 | 0.026
|  $\alpha$-investing | 81.5 | 0.87 | 0.08 | 0.044
|  $\alpha$-rewards $k=1$ | 80.7 | 0.85 | 0.08 | 0.042
|  $\alpha$-rewards $k=1.1$ | 80.4 | 0.81 | 0.07 | 0.039
|  ERO investing | 82.7 | 0.92 | 0.10 | 0.050
other | LORD++ | 934.9 | 2.59 | 0.06 | 0.015
| LORD1 | 1000.0 | 1.45 | 0.03 | 0.014
| LORD2 | 1000.0 | 2.00 | 0.06 | 0.020
| LORD3 | 1000.0 | 2.72 | 0.07 | 0.020
| SAFFRON | 1000.0 | 1.64 | 0.09 | 0.035
cost-aware |  ERO $n_{j}=1$ | 410.2 | 4.26 | 0.22 | 0.040
cost-aware |  ERO $n_{j}\leq 10$ | 139.3 | 13.15 | 0.24 | 0.017
cost-aware |  ERO $n_{j}\leq 100$ | 99.6 | 9.29 | 0.12 | 0.011
cost-aware |  ERO $n_{j}^{*}$ | 97.1 | 9.06 | 0.11 | 0.011
Table 2: Comparison of cost-aware $\alpha$-investing with state-of-the-art
sequential hypothesis testing methods. Values for Tests, True Rejects and
False Rejects are the average across 10,000 iterations, and these estimates
are used for mFDR.

Experimental Settings To compare our method with state-of-the-art related
methods, we generate synthetic data as described in Aharoni and Rosset,
(2014). The synthetic data is composed of $m=1000$ possible hypothesis tests.
For the $j$-th test, the true state of $\theta_{j}$ is set to the null value
of $0$ with probability $0.9$ and otherwise set to $2$. A set of $n_{j}=1000$
potential samples $(x_{ji})_{i=1}^{n_{j}}$ were generated i.i.d from a
$\mathcal{N}(\theta_{j},1)$ distribution. For each hypothesis test, the
z-score was computed as $z_{j}=\sqrt{n_{j}^{*}}\sum_{i=1}^{n_{j}^{*}}x_{ji}$,
where $n_{j}^{*}$ is described in the table and the one-sided p-value is
computed. The methods were tested on $10,000$ realizations of this simulation
data generation mechanism. Pseudo-code, as well as other implementation
details, for this simulation can be found in Appendix B.

###  5.1 Comparison to state-of-the-art methods

Table 2 compares our method, cost-aware ERO, with related state-of-the-art
$\alpha$-investing methods including: $\alpha$-spending (Tukey and Braun,,
1994), $\alpha$-investing (Foster and Stine,, 2008), $\alpha$-rewards (Aharoni
and Rosset,, 2014), ERO-investing (Aharoni and Rosset,, 2014), LORD (Javanmard
and Montanari,, 2018; Ramdas et al.,, 2017), and SAFFRON (Ramdas et al.,,
2018). The table is indexed by the allocation scheme (Scheme), and the reward
method (Method). The allocation scheme determines the value of $\varphi_{j}$
at each step. The constant scheme simply allocates,

$\varphi_{j}=\min\left\\{\frac{1}{10}W_{\alpha}(0),W_{\alpha}(j-1)\right\\},$

for each test, the relative scheme allocates an amount that is proportional to
the remaining $\alpha$-wealth,

$\varphi_{j}=\frac{1}{10}W_{\alpha}(j-1)$

and continues until $W_{\alpha}(j)<(1/1000)W_{\alpha}(0)$. The relative 200
scheme follows the same proportional steps as the relative, but always
performs 200 tests (Aharoni and Rosset,, 2014). The results from our
implementation of these methods matches or exceeds previously reported
results.

ERO investing yields more true rejects than $\alpha$-spending,
$\alpha$-investing, and both $\alpha$-rewards methods. The LORD variants and
SAFFRON perform nearly 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 to $n_{j}\leq 10$ enables cost-aware ERO to achieve
higher power with fewer tests than the current state-of-the-art methods.
Releasing the restriction on sample size enables cost-aware ERO to allocate
the optimal number of samples based on the prior of the null as well as the
available budget and the method returns an optimal $n_{j}^{*}$. 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_{j}\leq
10$ performs more tests and rejects more false null hypotheses than all
competing methods. We note, that the difference between restricting $n_{j}\leq
100$ and not restricting $n_{j}$ is rather small. For most of the tests, the
sample sizes chosen are quite similar, but differences appear when
$\alpha$-wealth becomes small, and the optimal sample size without restriction
is above 100.

Figure 2: Power, mFDR, and mean number of samples per test for cost-aware ERO
and existing methods with random $q_{j}$.

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
$\varphi_{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 $\alpha$-wealth (as a martingale). The
experimental set up of Aharoni and Rosset, (2014) implicitly leverages similar
prior knowledge in the spending schemes proposed. All spending schemes
proposed in Aharoni and Rosset, (2014) allow us to test at least one true
alternative, in expectation, at which point the $\alpha$-wealth should
increase. This increase in $\alpha$-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 $\rho_{j}$ with a large sample
size, and influence $W_{\alpha}(j)$ towards being submartingale. On the other
hand, nature’s equalizing strategy limits the expected payout to 0, by
limiting the size of $\varphi_{j}$, preventing the experimenter from
experiencing $\alpha$-death quickly, as seen in the constant spending scheme.

###  5.2 Computation and Implementation

In our experiments, for one set of $1,000$ potential hypothesis tests ERO
investing, cost-aware, and finite-horizon cost-aware ERO all take $\sim 30$
seconds on a single 2.5GHz core and 16Gb RAM. The nonlinear optimization
problem was solved using CONOPT (Drud,, 1994). 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.

Figure 3: Power, mFDR, and mean number of samples per test for finite horizon
cost-aware ERO with random $q_{j}$. A larger horizon corresponds to a greater
number of future tests considered in the optimization process.

###  5.3 Random Prior of the Null Hypothesis

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}\sim\text{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 2(a-c) shows the power, mFDR, and mean
number of samples per test as a function of $\mathbb{E}[q_{j}]$. The results
show that cost-aware ERO $\alpha$-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 $\alpha$-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_{\alpha}(j)$ towards
behaving as a supermartingale. Cost-aware ERO will compensate by increasing
$\rho_{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 $\mathbb{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.3) creates. The value of
$\varphi_{j}$ is kept small so that multiple false null hypotheses are tested
at an appreciable level so that $\alpha$-wealth can be earned, and testing
sustained. This setting is common in biological settings, where false null
hypotheses can be rare.

###  5.4 Finite-Horizon Cost-aware ERO Investing

To test whether extending the horizon of the reward to be maximized would
enable better decisions as to $(\alpha,\$)$-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. All methods were limited to
allocating $10$ samples at most to each individual test.

As seen in Figure 3, extending the horizon to include more tests results in a
more conservative allocation of samples. For $\mathbb{E}[q]=0.9$, which we
consider most applicable to biological applications, Table 3 shows that this
risk aversion increased the number of tests for smaller horizons, and then
decreases for larger horizons.

| Tests | True Rejects | False Rejects | mFDR
---|---|---|---|---
Horizon |  |  |  |
1 | 133.5 | 8.61 | 0.20 | 0.020
2 | 212.8 | 6.15 | 0.16 | 0.022
3 | 109.4 | 4.32 | 0.17 | 0.032
4 | 99.2 | 3.13 | 0.16 | 0.038
5 | 99.8 | 3.17 | 0.16 | 0.038
Table 3: Varying the size of the finite horizon when $q_{j}\sim Beta(90,10)$.
Values displayed correspond to the mean across 2,500 repetitions.

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. Despite this, the risk averse effect on the
initial test, in which $W_{\alpha}(j-1)$ is fixed and known, remains. An
unintended consequence of this risk aversion is a decrease in power. These
results demonstrate that our principled $(W_{\alpha},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.

Figure 4: Comparison of Cost-aware ERO investing and ERO investing for a
single permutation of the prostate cancer gene expression data. Cost-aware ERO
distributes the finite allocation of samples across the set of genes while ERO
expends the sample allocation within the first 20 tests. The sample lack of a
rejection for cost-aware ERO at test 8 is a result of a noisy estimate of
$q_{8}$, leading the algorithm to not allocate fewer than 50 samples. However,
this restraint in allocating sames allows for rejections at tests 24, 25, and
29.

##  6 REAL DATA EXPERIMENTS

Biological experimentation involves non-trivial sample costs, and the
proportion of false null hypotheses is typically small, while the number of
overall tests is quite large. Our methods were compared to the ERO method on
two gene expression data sets. The subsequent results demonstrate that our
cost-aware method performs more tests and rejections in such settings, while
spending less samples than a method which does not have the capability to
simultaneously optimize sample size.

###  6.1 Prostate Cancer Data

Gene expression data was collected to investigate the molecular determinants
of prostate cancer (Dettling,, 2004). 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 normal samples be denoted $\hat{\mu}_{j}$ and
$\hat{\sigma}_{j}$ respectively. The goal is to test whether the tumor gene
expression is increased relative to the normal samples.

A logistic function using only the first two samples for each gene was used to
compute the prior probability of the null hypothesis
$q_{j}=1-\left(1+\exp(-\beta([\bar{x_{j}}]_{1:2}-x_{0}))\right)^{-1}$, where
$x_{0}=\log_{10}(4)/\sigma$ and $\beta=2$; these first two samples were then
removed from the data set. The set of genes was permuted randomly and the
cost-aware decision function was computed for each gene in sequence with
$q_{j}$ as described and $\bar{\theta}_{j}=\log_{10}(2)/\hat{\sigma}_{j}$. For
cost-aware ERO the sample size was limited to $50$ samples. A one-sided
Gaussian test was performed with the optimal number of samples. This procedure
is compared to ERO investing with the maximum number of samples for all tests
that were selected to be performed by that procedure. For both procedures
$c_{j}=1,\forall j$, and $W_{\$}[0]=1000$. Pseudo-code and implementation
details for this experiment can be found in Appendix B.

Figure 4 shows a single run of the cost-aware and ERO decision rules on the
gene expression data set. The ERO method selects many tests, but rapidly
expends $W_{\$}$, as it does not optimize the sample size. In contrast, cost-
aware ERO is more conservative in sample allocation. Across 1000 permutations
of the data cost-aware ERO performed, on average, 26.0 tests and for the tests
that were performed, the average sample size was 38.9.

|  | Tests | Rejections | Avg. Cost
---|---|---|---|---
Data set | Method |  |  |
Prostate Cancer | ERO | 20 | 4.55 | 1000
| CAERO | 26 | 4.95 | 1000
LINCS | ERO | 90 | 32.68 | 100000
| CAERO | 162 | 39.41 | 76124
Table 4: Real data analysis results. Values displayed represent the average
across 1,000 permutations of each data set. Cost-aware ERO (CAERO) performs
more tests and rejects more hypotheses than ERO. In the LINCS data set, this
occurs with a large cost savings.

###  6.2 LINCS L1000

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
(geo). 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.
cyclegan infer the remaining genes using a CycleGAN and make the predictions
available on their lab’s webpage111https://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 $23614$ 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-\left(1+\exp(-\beta([\bar{x_{j}}]_{1:2}-x_{0}))\right)^{-1}$, where
$x_{0}=2/\sigma$ and $\beta=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,\forall j$, and $W_{\$}[0]=100000$ Our method was allowed
up to the remaining $1120$ samples while the ERO used all possible $1120$
samples. The order of genes was randomly shuffled before testing. One sided
Gaussian tests were performed where $\mu_{0}=0$ and $\mu_{A}=0.5$. $\sigma=1$
is assumed since data arrives standardized.

Table 4 shows that our method (CAERO) results in a larger number of tests and
a larger number of rejections, all while the average experimental cost is
lower. The mean number of samples used for an individual test is about
$n=580$. This shows that our algorithm selects a portion of the data so that
$\$$-spending is balanced against the increase in the likelihood of a
rejection for future $\alpha$-wealth.

It should be noted that the number of rejections is rather high for both
methods. This is likely a result of our use of statistical significance versus
clinical significance. With $n=1120$, the sampling distribution of $\bar{X}$
is $N(0,\frac{1}{\sqrt{1120}})$. Even small differences in $\mu_{A}$ will
cause the null hypothesis to be rejected. Since cost-aware ERO utilizes a more
reasonable sample size, we expect that these rejections are more likely to
contain true signal in comparison the set of rejections given by the ERO
method.

##  7 DISCUSSION

We have introduced an ERO generalized $\alpha$-investing procedure that has a
self contained decision rule. This rule removes the need for a user-specified
allocation scheme and optimally selects the sample size for each test. We have
shown empirical results in support of the benefits of optimizing these testing
parameters rather than being left to user choice. An experiment with gene
expression data shows that we can conduct more tests than with previous
methods. The negative societal impact and ethical concerns of this work are
limited, as this work proposes a method to control for multiple testing.

There are some limitations of the current work. First, the cost-aware ERO
method may be sensitive to misspecification in $q_{j}$. Simulations with an
increasing distance between the true $q_{j}$ and that used by the cost-aware
ERO method show that cost-aware ERO performance degrades for misspecified
values of $q_{j}$ (Appendix E), however, mFDR control is not affected.
Specification of $q_{j}$ should reflect the belief that an individual
hypothesis belongs to the null hypothesis, and such granular information is
not always available. We have demonstrated potential methods to estimate such
quantities in real data simulations. It is also possible to set $q_{j}$ to be
a more coarse belief of the distribution of hypotheses. For example, if it is
believed that hypotheses are generated with a spike and slab distribution, it
is reasonable to set $q_{j}$ to the probability mass of the spike. Such
information is already captured in the relative spending scheme of ERO and the
$\gamma$ vector in LORD.

Second, the finite horizon method requires many known values $q_{j}$. In a
streaming situation this information may not be available. This may be
alleviated by dynamically adjusting the size of the horizon as hypotheses
arrive. However, we acknowledge that this presents a further complication in
the implementation of our method, and opens the question of optimizing the
size of the horizon, which is beyond the scope of the current work.

Finally, cost-aware ERO does not have an explicit mechanism to hedge the risk
of dollar wealth or $\alpha$-wealth loss. In our simulations we observed that
cost-aware ERO can choose to ante ($\varphi_{j}$) the entire pool of
$\alpha$-wealth on the first promising test in the hopes of maximizing the
expected reward. While this strategy is certainly one that maximizes the
expected reward, it may be too risky in practice. One solution is to constrain
$\varphi_{j}$ for any single test or to include $\varphi_{j}$ in the objective
function. We rectify this with the addition of $a$ in constraint (4.3),
although the setting of $a$ presents an additional parameter to select
a-priori. The current optimization problem assumes a risk-neutral player who
wishes to not lose $\alpha$-wealth, on average, when conducting a test. Since
this desire is expressed in expectation, the variance of actual outcomes can
be large, leading to $\alpha$-death. For future work, it would be interesting
to investigate a principled risk-hedging approach to conserve some wealth for
future tests with the hope that a test with a more favorable reward structure
is over the horizon.

## References

  * Aharoni and Rosset, (2014) Aharoni, E. and Rosset, S. (2014).  Generalized $\alpha$-investing: definitions, optimality results and application to public databases.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 76(4):771–794.
  * Arrow et al., (1949) Arrow, K. J., Blackwell, D., and Girshick, M. A. (1949).  Bayes and minimax solutions of sequential decision problems.  Econometrica, Journal of the Econometric Society, pages 213–244.
  * Benjamini and Hochberg, (1995) Benjamini, Y. and Hochberg, Y. (1995).  Controlling the false discovery rate: a practical and powerful approach to multiple testing.  Journal of the Royal statistical society: series B (Methodological), 57(1):289–300.
  * Benjamini et al., (2006) Benjamini, Y., Krieger, A. M., and Yekutieli, D. (2006).  Adaptive linear step-up procedures that control the false discovery rate.  Biometrika, 93(3):491–507.
  * Berger, (2013) Berger, J. O. (2013).  Statistical decision theory and Bayesian analysis.  Springer Science & Business Media.
  * Blackwell and Girshick, (1979) Blackwell, D. A. and Girshick, M. A. (1979).  Theory of games and statistical decisions.  Courier Corporation.
  * Chen and Kasiviswanathan, (2020) Chen, S. and Kasiviswanathan, S. (2020).  Contextual online false discovery rate control.  In International Conference on Artificial Intelligence and Statistics, pages 952–961. PMLR.
  * Dettling, (2004) Dettling, M. (2004).  Bagboosting for tumor classification with gene expression data.  Bioinformatics, 20(18):3583–3593.
  * Dickey and Lientz, (1970) Dickey, J. M. and Lientz, B. (1970).  The weighted likelihood ratio, sharp hypotheses about chances, the order of a markov chain.  The Annals of Mathematical Statistics, pages 214–226.
  * Drud, (1994) Drud, A. S. (1994).  Conopt—a large-scale grg code.  ORSA Journal on computing, 6(2):207–216.
  * Foster and Stine, (2008) Foster, D. P. and Stine, R. A. (2008).  $\alpha$-investing: a procedure for sequential control of expected false discoveries.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70(2):429–444.
  * Javanmard and Montanari, (2018) Javanmard, A. and Montanari, A. (2018).  Online rules for control of false discovery rate and false discovery exceedance.  The Annals of statistics, 46(2):526–554.
  * Liang and Nettleton, (2012) Liang, K. and Nettleton, D. (2012).  Adaptive and dynamic adaptive procedures for false discovery rate control and estimation.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 74(1):163–182.
  * Parmigiani and Inoue, (2009) Parmigiani, G. and Inoue, L. (2009).  Decision theory: Principles and approaches.  John Wiley & Sons.
  * Ramdas et al., (2019) Ramdas, A., Chen, J., Wainwright, M. J., and Jordan, M. I. (2019).  A sequential algorithm for false discovery rate control on directed acyclic graphs.  Biometrika, 106(1):69–86.
  * Ramdas et al., (2017) Ramdas, A., Yang, F., Wainwright, M. J., and Jordan, M. I. (2017).  Online control of the false discovery rate with decaying memory.  Advances in neural information processing systems, 30.
  * Ramdas et al., (2018) Ramdas, A., Zrnic, T., Wainwright, M., and Jordan, M. (2018).  Saffron: an adaptive algorithm for online control of the false discovery rate.  In International conference on machine learning, pages 4286–4294. PMLR.
  * Storey, (2002) Storey, J. D. (2002).  A direct approach to false discovery rates.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 64(3):479–498.
  * Storey et al., (2004) Storey, J. D., Taylor, J. E., and Siegmund, D. (2004).  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.
  * Tukey, (1991) Tukey, J. W. (1991).  The philosophy of multiple comparisons.  Statistical science, pages 100–116.
  * Tukey and Braun, (1994) Tukey, J. W. and Braun, H. (1994).  The Collected Works of John W. Tukey: Multiple Comparions, Volume VIII, volume 8.  Elsevier.
  * Verdinelli and Wasserman, (1995) Verdinelli, I. and Wasserman, L. (1995).  Computing bayes factors using a generalization of the savage-dickey density ratio.  Journal of the American Statistical Association, 90(430):614–618.
  * Xia et al., (2017) Xia, F., Zhang, M. J., Zou, J. Y., and Tse, D. (2017).  NeuralFDR: Learning discovery thresholds from hypothesis features.  Advances in neural information processing systems, 30.
  * Yang et al., (2017) Yang, F., Ramdas, A., Jamieson, K. G., and Wainwright, M. J. (2017).  A framework for multi-a (rmed)/b (andit) testing with online fdr control.  Advances in Neural Information Processing Systems, 30.
  * Zeisel et al., (2011) Zeisel, A., Zuk, O., and Domany, E. (2011).  Fdr control with adaptive procedures and fdr monotonicity.  The Annals of applied statistics, pages 943–968.
  * Zrnic et al., (2021) Zrnic, T., Ramdas, A., and Jordan, M. I. (2021).  Asynchronous online testing of multiple hypotheses.  J. Mach. Learn. Res., 22:33–1.

##  Appendix A THEORETICAL ANALYSIS OF LONG-TERM ALPHA-WEALTH AND COST-AWARE
ERO SOLUTION

###  A.1 Proof of Lemma 1

###### Proof of Lemma 1.

The expected increment in $\alpha$-wealth is

$\mathbb{E}[W_{\alpha}(j)-W_{\alpha}(j-1)]=\mathbb{E}[R_{j}]\alpha-\mathbb{E}[1-R_{j}]\frac{\alpha_{j}}{1-\alpha_{j}}.$

This equation requires the probability of rejection, which can be written in
factorized form as

$\Pr(R_{j}=1)=\Pr(R_{j}=1|\theta_{j}\in H_{j})\Pr(\theta_{j}\in
H_{j})+\Pr(R_{j}=1|\theta_{j}\not\in H_{j})\Pr(\theta_{j}\not\in H_{j}).$

Now, $\Pr(R_{j}=1|\theta_{j}\in H_{j})\leq\alpha_{j}$ by Assumption 1 and
$\Pr(R_{j}=1|\theta_{j}\not\in H_{j})\leq\rho_{j}$ by Assumption 2. Defining
$\Pr(\theta_{j}\in H_{j})=q_{j}$ gives the result. ∎

###  A.2 Proof of Theorem 1

###### Proof.

Since $\Theta_{j}=\\{0,\bar{\theta}_{j}\\}$, by lemma 1 we have

$\mathbb{E}\left[W_{\alpha}(j)-W_{\alpha}(j-1)\mid
W_{\alpha}(j-1)\right]=-\frac{\alpha_{j}}{1-\alpha_{j}}+\left[\rho_{j}-\left(\rho_{j}-\alpha_{j}\right)q_{j}\right]\left(\alpha+\frac{\alpha_{j}}{1-\alpha_{j}}\right)$

We define $M_{j}:=\rho_{j}-(\rho_{j}-\alpha_{j})q_{j}$, then
$\\{W_{\alpha}(j):j\in\mathbb{N}\\}$ is submartingale, if and only if

$M_{j}\geq\frac{\alpha_{j}/(1-\alpha_{j})}{\alpha+\alpha_{j}/(1-\alpha_{j})}.$

Since $M_{j}=\rho_{j}-(\rho_{j}-\alpha_{j})q_{j}>\rho_{j}(1-q_{j})$, thus
$\\{W_{\alpha}(j)\\}$ is submartingale if

$\rho_{j}\geq\frac{\alpha_{j}/(1-\alpha_{j})}{\alpha+\alpha_{j}/(1-\alpha_{j})}\frac{1}{1-q_{j}}.$

∎

###  A.3 Proof of Theorem 2

###### Proof.

Let $M_{j}:=\rho_{j}-(\rho_{j}-\alpha_{j})q_{j}$, by Lemma 1,
$\\{W_{\alpha}(j):j\in\mathbb{N}\\}$ is supermartingale, if

$M_{j}\leq\frac{\alpha_{j}/(1-\alpha_{j})}{\alpha+\alpha_{j}/(1-\alpha_{j})}.$
(18)

Next we define $s_{j}\in[0,(1-\alpha_{j})/\alpha_{j}]$, a positive number to
control how large the power is for the $j$th test, such that

$\rho_{j}=s_{j}\alpha_{j}/(1-\alpha_{j})$

And we have

$\rho_{j}-\alpha_{j}=[(s_{j}-1)\alpha_{j}+\alpha_{j}^{2}]/(1-\alpha_{j})\geq(s_{j}-1)\alpha_{j}/(1-\alpha_{j}).$

Thus,

$M_{j}\leq\frac{s_{j}\alpha_{j}}{1-\alpha_{j}}-\frac{(s_{j}-1)\alpha_{j}}{1-\alpha_{j}}q_{j}.$

The condition in (18) becomes

$\frac{1-\alpha_{j}}{\alpha_{j}}M_{j}\leq
s_{j}-(s_{j}-1)q_{j}=s_{j}(1-q_{j})+q_{j}\leq\frac{1}{\alpha+\alpha_{j}/(1-\alpha_{j})}.$

Thus, for a given $q_{j}$, the condition on $s_{j}$ for stochastically non-
increasing wealth is

$s_{j}\leq\left(\frac{1}{\alpha+\alpha_{j}/(1-\alpha_{j})}-q_{j}\right)/(1-q_{j}).$
(19)

The upper-bound in condition (19) is valid if it is positive. For $j$ large
enough, if $\alpha_{j}/(1-\alpha_{j})<\alpha$, then

$\frac{1}{\alpha+\alpha_{j}/(1-\alpha_{j})}-q_{j}>\frac{1}{2\alpha}-q_{j}.$

If $\alpha_{j}<1/2$, this term is positive and the upper-bound for $s_{j}$ is
positive. ∎

###  A.4 Proof of Theorem 3

###### Proof.

Following the notation of Aharoni and Rosset, (2014), the expected increment
in $\alpha$-wealth is

$\mathbb{E}[W_{\alpha}(j)-W_{\alpha}(j-1)|W_{\alpha}(j-1)]=\mathbb{E}[R_{j}|\\{R_{1},\dots,R_{j-1}\\}](-\varphi+\psi_{j})-\mathbb{E}[1-R_{j}|\\{R_{1},\dots,R_{j-1}\\}](-\varphi).$
(20)

By definition, $\alpha$-wealth is martingale when this increment is equal to
$0$. Next, let $\mathbb{E}^{j-1}[X]=\mathbb{E}(X|\\{X_{1},\dots,X_{j-1}\\}$.
Then equation 20 becomes:

$0=\mathbb{E}^{j-1}[R_{j}](-\varphi+\psi_{j})+\mathbb{E}^{j-1}[1-R_{j}](-\varphi)$
(21)

Expanding $\mathbb{E}^{j-1}[R_{j}]$ in terms of variables in equation 4.3
gives

$\mathbb{E}^{j-1}[R_{j}]=\Pr(R_{j}=1)=\Pr(R_{j}=1|\theta_{j}\in
H_{j})\Pr(\theta_{j}\in H_{j})+\Pr(R_{j}=1|\theta_{j}\not\in
H_{j})\Pr(\theta_{j}\not\in H_{j}).$

By our previous assumptions, $\Pr(R_{j}=1|\theta_{j}\in H_{j})\leq\alpha_{j}$
and $\Pr(R_{j}=1|\theta_{j}\not\in H_{j})\leq\rho_{j}$. We define
$\Pr(\theta_{j}\in H_{j})=q_{j}$, and hence $\Pr(\theta_{j}\not\in
H_{j})=1-q_{j}$.

Simplifying equation 21 yields

$0=(q_{j}\alpha_{j}+(1-q_{j})\rho_{j})(-\varphi_{j}+\psi_{j})+(q_{j}(1-\alpha_{j})+(1-q_{j})(1-\rho_{j}))(-\varphi_{j})$
(22)

Solving equation 22 for $\rho_{j}$

$\rho_{j}=\left(\frac{1}{1-q_{j}}\right)\left(\frac{\varphi_{j}}{\psi_{j}}-q_{j}\alpha_{j}\right)$

This implies that
$\rho_{j}\propto\frac{\varphi_{j}}{\psi_{j}}-q_{j}\alpha_{j}$. This implies
that the power of the test must balance the probability of rejection under the
null and the ratio of the cost and reward of the test. ∎

###  A.5 Existence and Uniqueness of Solution

Since the solution to the cost-aware ERO problem is infact an ERO solution,
the existence of a solution is proven in Lemma 2 of Aharoni and Rosset, (2014)
given some assumptions which hold for a uniformly most powerful test with a
continuous distribution function. Since these are the types of tests being
considered in the current work, the necessary assumptions are met.

######  Theorem 4.

In the cost-aware ERO solution, $\varphi$ is unique.

###### Proof.

Suppose $\exists$ a solution
$(\varphi_{j}^{*},\psi_{j}^{*},\alpha_{j}^{*},\rho_{j}^{*},n_{j}^{*})$ such
that

$\mathbb{E}(R_{j})\psi_{j}=\mathbb{E}(R_{j})^{*}\psi_{j}^{*}.$ (23)

Expanding the expectation of rejections in equation 23 yields

$(q_{j}\alpha_{j}+(1-q_{j})\rho_{j})\psi_{j}=(q_{j}\alpha_{j}^{*}+(1-q_{j})\rho_{j}^{*})\psi_{j}^{*}.$
(24)

As per Lemma 2, the $\alpha$-wealth is martingale when using a solution to the
cost-aware ERO optimization problem. Applying theorem 3 gives

$\rho_{j}=\left(\frac{1}{1-q_{j}}\right)\left(\frac{\varphi_{j}}{\psi_{j}}-q_{j}\alpha_{j}\right)$
(25)
$\rho_{j}^{*}=\left(\frac{1}{1-q_{j}}\right)\left(\frac{\varphi_{j}^{*}}{\psi_{j}^{*}}-q_{j}\alpha_{j}^{*}\right).$
(26)

Substituting equations 25 and 26 into equation 24 gives

$q_{j}\alpha_{j}+(1-q_{j})\left(\left(\frac{1}{1-q_{j}}\right)\left(\frac{\varphi_{j}}{\psi_{j}}-q_{j}\alpha_{j}\right)\right)\psi_{j}=q_{j}\alpha_{j}^{*}+(1-q_{j})\left(\left(\frac{1}{1-q_{j}}\right)\left(\frac{\varphi_{j}^{*}}{\psi_{j}^{*}}-q_{j}\alpha_{j}^{*}\right)\right)\psi_{j}^{*}$
(27)
$\left(q_{j}\alpha_{j}+\frac{\varphi_{j}}{\psi_{j}}-q_{j}\alpha_{j}\right)\psi_{j}=\left(q_{j}\alpha_{j}^{*}+\frac{\varphi_{j}^{*}}{\psi_{j}^{*}}-q_{j}\alpha_{j}^{*}\right)\psi_{j}^{*}$
(28)
$\left(\frac{\varphi_{j}}{\psi_{j}}\right)\psi_{j}=\left(\frac{\varphi_{j}^{*}}{\psi_{j}^{*}}\right)\psi_{j}^{*}$
(29) $\varphi_{j}=\varphi_{j}^{*}$ (30)

∎

Since the sample size, $n_{j}$ is now made a free parameter, a natural
question is whether or not a unique $n_{j}$ can be selected. This is not
necessarily the case. Consider the solution
$(\varphi_{j},\psi_{j},\alpha_{j},\rho_{j},n_{j})$ to the cost-aware ERO
problem. Assume that a continuous distribution function is used. We now show
that $(\psi_{j},\alpha_{j},\rho_{j},n_{j})$ are not necessarily unique.

Suppose $\exists$ a solution
$(\varphi_{j}^{*},\psi_{j}^{*},\alpha_{j}^{*},\rho_{j}^{*},n_{j}^{*})$ such
that

$\mathbb{E}(R_{j})\psi_{j}=\mathbb{E}(R_{j})^{*}\psi_{j}^{*}.$ (31)

From equation 30, we know that $\varphi_{j}=\varphi_{j}^{*}$. From Aharoni and
Rosset, (2014), any solution that is ERO must satisfy

$\frac{\varphi_{j}}{\rho_{j}}=\frac{\varphi_{j}}{\alpha_{j}}-1.$ (32)

Using equation 32 it follows that

$\frac{\varphi_{j}^{*}}{\rho_{j}^{*}}=\frac{\varphi_{j}^{*}}{\alpha_{j}^{*}}-1.$
(33)

Solving equations 32 and 33 for $\varphi_{j}$ and $\varphi_{j}^{*}$
respectively give

$\varphi_{j}=\frac{1}{\frac{1}{\alpha_{j}}-\frac{1}{\rho_{j}}}$ (34)
$\varphi_{j}^{*}=\frac{1}{\frac{1}{\alpha_{j}^{*}}-\frac{1}{\rho_{j}^{*}}}$
(35)

Substituting equations 34 and 35 into equation 30 gives

$\frac{1}{\frac{1}{\alpha_{j}}-\frac{1}{\rho_{j}}}=\frac{1}{\frac{1}{\alpha_{j}^{*}}-\frac{1}{\rho_{j}^{*}}}$
(36)

Simplifying gives

$\frac{1}{\alpha_{j}}-\frac{1}{\alpha_{j}^{*}}=\frac{1}{\rho_{j}}-\frac{1}{\rho_{j}^{*}}$
(37)

Suppose $\alpha_{j}^{*}>\alpha_{j}$. It follows that $\rho_{j}^{*}>\rho_{j}$.
Without loss of generality (with respect to the test statistic having a
continuous distribution function), assume the test statistic is normally
distributed. Writing out $\rho_{j}$ and $\rho_{j}^{*}$ explicitly then implies
that

$1-\Phi\left(z_{1-\alpha_{j}^{*}}-\frac{\bar{\theta_{j}}}{\frac{\sigma_{j}}{\sqrt{n_{j}^{*}}}}\right)>1-\Phi\left(z_{1-\alpha_{j}}-\frac{\bar{\theta_{j}}}{\frac{\sigma_{j}}{\sqrt{n_{j}}}}\right)$
(38)
$z_{1-\alpha_{j}^{*}}-\frac{\bar{\theta_{j}}}{\frac{\sigma_{j}}{\sqrt{n_{j}^{*}}}}<z_{1-\alpha_{j}}-\frac{\bar{\theta_{j}}}{\frac{\sigma_{j}}{\sqrt{n_{j}}}}$
(39)
$\frac{\bar{\theta_{j}}}{\frac{\sigma_{j}}{\sqrt{n_{j}}}}-\frac{\bar{\theta_{j}}}{\frac{\sigma_{j}}{\sqrt{n_{j}^{*}}}}<z_{1-\alpha_{j}}-z_{1-\alpha_{j}^{*}}$
(40)
$\sqrt{n_{j}}-\sqrt{n_{j}^{*}}<\frac{\sigma_{j}}{\bar{\theta_{j}}}\left(z_{1-\alpha_{j}}-z_{1-\alpha_{j}^{*}}\right)$
(41)

Equation 41 shows that a range on $n$ values can be used. In certain
scenarios, this allows
$(\psi_{j},\alpha_{j},\rho_{j},n_{j})\neq(\psi_{j}^{*},\alpha_{j}^{*},\rho_{j}^{*},n_{j}^{*})$.
Considering the case when $\alpha_{j}^{*}<\alpha_{j}$ results in equation 41
having the inequality reversed. Note that $n_{j}=1$ is not necessarily
permitted by this range. Including $n_{j}$ in our problem is still useful,
despite not being unique, since an a-priori specification may not yield the
same maximal expected reward as leaving $n_{j}$ to be optimized.

##  Appendix B SIMULATION DETAILS

In this section we describe simulations in greater detail so that our work can
be fully reproduced. We briefly present the cost-aware ERO $\alpha$-investing
method in algorithmic form.

Input $\alpha$, $W_{\alpha}(0)$, $W_{\$}(0)$

$j\leftarrow 0$

while $W_{\alpha}(j)>\epsilon$ and $W_{\$}(j)>\epsilon$ do

Define $q_{j}$, $c_{j}$ for hypothesis $j$

Solve Problem 18 to obtain $\varphi_{j}$, $\alpha_{j}$, $\rho_{j}$,
$\psi_{j}$, and $n_{j}$

Collect data $(x_{j1},\ldots,x_{jn_{j}})$ and compute p-value $p_{j}$.

if $p_{j}\leq\alpha_{j}$ then

$R_{j}\leftarrow 1$

else

$R_{j}\leftarrow 0$

end if

Update $W_{\$}(j+1)\leftarrow W_{\$}(j)-c_{j}n_{j}$

Update $W_{\alpha}(j+1)\leftarrow W_{\alpha}(j)-\varphi_{j}+R_{j}\psi_{j}$

$j\leftarrow j+1$

end while

Algorithm 1 Cost-aware ERO Algorithm

###  B.1 Experiment for Table 2

For cost-aware ERO, the initial value of $\alpha_{j}$ was set $0.001$, and the
initial value of $\rho_{j}$ was set to $0.9$. These initial values tended to
give more conservative allocations of sample size as the optimal value of
$\rho_{j}$ often approached a value of $1$. In our simulation we define
$\alpha=0.05$, $W_{\alpha}(0)=0.0475$, $W_{\$}(0)=1000$, $n_{iter}=10000$
(number of iterations), $m=1000$ (maximum number of tests per iteration), and
$c=1$ (cost per sample). $W_{\alpha}(0)$ for implementations of LORD and
SAFFRON follow suggestions from Javanmard and Montanari, (2018) and Ramdas et
al., (2018). An explicit algorithm is given in Algorithm 2. A similar
experimental set up is used for Table 5 and Table 7 where $q_{j}$ and $n_{j}$
are adjusted respectively.

Algorithm 2 Simulation run in Table 2

Input $\alpha$, $W_{\alpha}(0)$, $W_{\$}(0)$, $n_{iter}$, $m$, $c$

for $i=0$ to $i=n_{iter}$ do

Set seed to $i$

$\boldsymbol{X}=$ [ ]

for $j=0$ to $m$ do

Sample $\theta_{j}$, with $Pr(\theta_{j}=0)=q_{j}=0.9$, and
$Pr(\theta_{j}=2)=1-q_{j}=0.1$.

$\boldsymbol{X}[j]=1000$ realizations from $N(\theta_{j},1)$.

end for

for each testing method (unique row in Table 2) do

$j\leftarrow 0$

while $W_{\alpha}(j)>\epsilon$ and $W_{\$}(j)>\epsilon$ do

$n_{j}=1$ $\triangleright$ Sample size to use if method not cost-aware.

if Spending and Investing rule separate then

Obtain $\varphi_{j}$ from spending scheme.

Obtain $\alpha_{j}$, $\psi_{j}$ from investing rule $\mathcal{I}$

else

Obtain $\varphi_{j}$, $\alpha_{j}$, $\psi_{j}$ from self-contained investing
rule $\mathcal{I}$. (If using cost-aware, obtain and update $n_{j}$).

end if

Perform 1-sided $Z$-test on $\boldsymbol{X}[j][0:n_{j}]$, and obtain
$p$-value, $p_{j}$.

if $p_{j}\leq\alpha_{j}$ then

$R_{j}\leftarrow 1$

else

$R_{j}\leftarrow 0$

end if

Update $W_{\$}(j+1)\leftarrow W_{\$}(j)-cn_{j}$

Update $W_{\alpha}(j+1)\leftarrow W_{\alpha}(j)-\varphi_{j}+R_{j}\psi_{j}$

$j\leftarrow j+1$

end while

end for

end for

Aggregate results

###  B.2 Experiment for Figure 2

We next discuss the experimental details for producing Figure 2. The initial
value for $\rho_{j}$ (and for $\rho_{j+1}$) was set to 1. Contrary to the
previous experiment, we desire to demonstrate that myopic allocation of
samples is avoided in finite-horizon ERO regardless of initial values. In our
simulation we define $\alpha=0.05$, $W_{\alpha}(0)=0.0475$, $W_{\$}(0)=1e8$,
$n_{iter}=2500$, $m=1000$, and $c=1$. An additional $q$, specifically
$q_{1001}$ is drawn for solving the finite-horizon optimization problem when
we reach the final test. We sample $q_{j}$ from a Beta$(a,100-a)$
distribution, and then sample whether $\theta_{j}$ is null or not based on the
realization of $q_{j}$. This sampling scheme and relevant parameter values are
given in Algorithm 3.

Algorithm 3 Simulation run in Figure 2

Input $\alpha$, $W_{\alpha}(0)$, $W_{\$}(0)$, $n_{iter}$, $m$, $c$

for $i=0$ to $i=n_{iter}$ do

Set seed to $i$

for $a\in\\{10,20,30,40,50,60,70,80,90\\}$ do

$\boldsymbol{X}=$ [ ]

for $j=0$ to $m$ do

Sample $q_{j}\sim Beta(a,100-a)$

Sample $\theta_{j}$, with $Pr(\theta_{j}=0)=q_{j}$, and
$Pr(\theta_{j}=2)=1-q_{j}$.

$\boldsymbol{X}[j]=1000$ realizations from $N(\theta_{j},1)$.

end for

for each testing method (unique row in Figure 2) do

while $W_{\alpha}(j)>\epsilon$ and $W_{\$}(j)>\epsilon$ do

Perform while loop in Algorithm 2.

end while

end for

end for

end for

Aggregate results

###  B.3 Experiment for Figure 4

The real data experiment shown in Figure 4 and detailed in Section 6 can be
broken down into two steps: preprocessing and testing.

In preprocessing, we load in two dataframes, one containing gene expression
data for 50 normal (non-cancerous) samples ($6033\times 50$), and a second
containing similar data for 52 tumor samples ($6033\times 52$). We take then
mean across the normal samples to obtain a ($6033\times 1$) vector containing
the mean gene expression for normal patients. We calculate the standard
deviation in a similar manner and use these vectors to standardize the
$(6033\times 52)$ dataframe containing tumor samples. Next, the first two
columns of the tumor samples dataframe is separated from the remaining 50
columns to provide an informed estimate of $q_{j}$ for each test. It is
important to note that we are allowing the potential for misspecification of
$q_{j}$ by using an estimate of only two samples. Using these two samples:

$q_{j}=1-\left(1+\exp(-\beta([\bar{x_{j}}]_{1:2}-x_{0}))\right)^{-1},$

where $x_{0}=\log_{10}(4)/\hat{\sigma}$, $\beta=2$, $[\bar{x_{j}}]_{1:2}$
denotes the sample mean of the two tumor samples separated from the remaining
50 tumor samples for the $j^{th}$ gene, and $\hat{\sigma}$ is the estimated
standard deviation from the normal samples.

During the testing process, we perform a random shuffle of the genes and then
run testing. This process is shown in Algorithm 4. In this scenario, we set
$\alpha=0.05$, $W_{\alpha}(0)=0.0475$, $W_{\$}(0)=1000$, $n_{iter}=1000$
(number of permutations), $m=6033$, and $c=1$. We set ERO investing to always
use a sample size of $n_{j}=50$. For cost-aware ERO, we set the initial value
of $\rho_{j}=0.9$ and do not set a restriction on the upper value of $n_{j}$.
However, if the optimized value is greater than 50, we choose to skip the
test. Lastly, we set the constraint of $\varphi_{j}\leq
0.5*(1-q_{j})W_{\alpha}(j)$ to avoid quick $\alpha$-death in some
permutations. We note that this does not affect tests with large $q_{j}$ very
much, as one might expect, since those tests require small bets in order to
remain keep nature’s strategy equalizing.

Algorithm 4 Simulation run in Figure 4

Input $\alpha$, $W_{\alpha}(0)$, $W_{\$}(0)$, $n_{iter}$, $m$, $c$

for $i=0$ to $i=n_{iter}$ do

Set seed to $i$

Randomly shuffle data

for Method $\in\\{$ ERO, cost-aware ERO $\\}$ do

while $W_{\alpha}(j)>\epsilon$ and $W_{\$}(j)>\epsilon$ do

if Method is cost-aware ERO then

Set constraint $\varphi_{j}\leq(1-q_{j})W_{\alpha}(j)$

Solve Problem 18 to obtain $\varphi_{j}$, $\alpha_{j}$, $\psi_{j}$, and
$n_{j}$

if $0<n_{j}\leq 50$ then

Perform test and update as per other simulations.

else

Skip test

end if

else

Perform test with sample size $n_{j}=50$ and update as per other simulations.

end if

end while

end for

end for

Aggregate results.

##  Appendix C EXTENSIONS OF COST-AWARE $\alpha$-INVESTING

In this section, we explore extensions of cost-aware ERO $\alpha$-investing.

###  C.1 Cost tradeoffs.

In Problem 4.3 the monetary cost does not factor in to the objective except
through the constraints. In many practical applications, it may be useful to
simultaneously maximize the $\alpha$-reward and minimize the $\$$-cost. In
those applications, the objective function can be augmented to
$\mathbb{E}(R_{j})\psi_{j}-\gamma c_{j}n_{j}$, where $\gamma$ controls the
trade-off between improving $\alpha$-wealth and minimizing $\$$-cost.

###  C.2 Variable utility.

Not all hypotheses may have equal value to the investigator and their value
assessment may be independent of their assessment of the prior probability of
the null hypothesis (Ramdas et al.,, 2017). For example, an investigator may
be confident that a gene is differentially expressed in a particular tissue
based on prior literature. Then the prior probability that $\theta_{j}=0$ is
low, $p_{j}\approx 0$, and the utility of testing that hypothesis is also low.
There may be a different gene that has not been reported to be differentially
expressed in the tissue, but if it is it would be a major scientific
discovery. Then, the investigator may assign a high prior probability to the
null $\theta_{j}=0$, but also a high utility to the event that the null is
rejected. A generalized form of the cost-aware decision rule can be
constructed to account for varying utility levels for each hypothesis in the
batch by making the objective function
$\sum_{j=1}^{K}\mathbb{E}_{\theta}(R_{j})U(R_{j})\psi_{j}$, where $U(R_{j})$
is the utility of the rejection of the $j$-th null hypothesis.

###  C.3 Batch testing.

Many biological experiments are conducted in batches. This scenario leads to a
need for a decision rule that provides $(\alpha_{j},\psi_{j},n_{j})_{j=1}^{K}$
for a batch of $K$ tests. To address this need, the objective function in
Problem 4.3 can be modified to
$\sum_{j=1}^{K}\mathbb{E}_{\theta}(R_{j})\psi_{j}$. It seems reasonable to
expend all of the $\alpha$-wealth for each batch and then collect the reward
at the completion of the batch so that a next batch of hypotheses can be
tested. Therefore, we have constraints $\sum_{j=1}^{K}\varphi_{j}\leq
W_{\alpha}(0)$ and $\sum_{j=1}^{K}c_{j}n_{j}\leq W_{\$}(0)$. The other
constraint remain and apply for each test in the batch.

##  Appendix D METHOD COMPARISON WITH $q=0.1$

In Table 5 we explore the comparison of cost-aware ERO investing with other
methods for $q_{j}=0.1$. The results presented in the main body of the paper
are for $q_{j}=0.9$ to align with previous work. Naturally, when nulls occur
infrequently, the issue of multiple testing is not as dire. When true
alternatives are abundant, cost-aware ERO requires a large ante
($\varphi_{j}$). In this simulation we set $a=1$ to highlight this effect.
This causes cost-aware ERO to rapidly deplete the $\alpha$-wealth. In
contrast, other methods do not increase the ante as severely as cost-aware
ERO. However, it should be noted that the fraction of the tests that are true
rejects among those that are performed is very high. For example, in constant
ERO investing the proportion of true rejects is 24% and the proportion of true
rejects for cost-aware ERO ($n_{j}\leq 10$) is 90%. This is a highly desirable
result for the setting of biological experiments and other settings where
sample cost is nontrivial.

|  | Tests | True Rejects | False Rejects | mFDR
---|---|---|---|---|---
Scheme | Method |  |  |  |
constant |  $\alpha$-spending | 10.0 | 2.49 | 0.00 | 0.001
|  $\alpha$-investing | 932.4 | 231.55 | 0.46 | 0.002
|  $\alpha$-rewards $k=1$ | 925.0 | 230.13 | 0.46 | 0.002
|  $\alpha$-rewards $k=1.1$ | 926.5 | 221.54 | 0.42 | 0.002
| ERO investing | 934.3 | 230.87 | 0.45 | 0.002
relative |  $\alpha$-spending | 66.0 | 4.95 | 0.00 | 0.001
|  $\alpha$-investing | 994.0 | 661.55 | 10.19 | 0.015
|  $\alpha$-rewards $k=1$ | 989.2 | 416.37 | 2.00 | 0.005
|  $\alpha$-rewards $k=1.1$ | 991.4 | 626.93 | 7.47 | 0.012
|  ERO investing | 994.8 | 820.57 | 34.14 | 0.040
other | LORD++ | 885.8 | 197.07 | 0.39 | 0.002
| LORD1 | 1000.0 | 93.81 | 0.07 | 0.001
| LORD2 | 1000.0 | 301.45 | 0.94 | 0.004
| LORD3 | 1000.0 | 271.22 | 0.68 | 0.003
| SAFFRON | 1000.0 | 779.92 | 23.92 | 0.030
cost-aware |  ERO $n_{j}=1$ | 11.1 | 9.94 | 0.15 | 0.013
cost-aware |  ERO $n_{j}\leq 10$ | 12.8 | 11.48 | 0.21 | 0.017
cost-aware |  ERO $n_{j}^{*}$ | 10.6 | 9.48 | 0.13 | 0.012
Table 5: Comparison of cost-aware $\alpha$-investing with state-of-the-art
sequential hypothesis testing methods with a prior probability of the null,
$q=0.1$ using 2,500 iterations. Cost-aware uses an initial $\rho_{j}$ for each
iteration of 1.

##  Appendix E SENSITIVITY ANALYSIS WITH RESPECT TO $q_{j}$

Since the cost-aware ERO method makes use of the prior probability of the null
hypothesis, $q_{j}$, we investigate the sensitivity of the method to
misspecification of that parameter. Table 6 shows the number of tests, mean
true rejects, mean false rejects, and mFDR for simulation where the $q_{j}$
provided for optimization is misspecified. Specifically, we vary the specified
$q_{j}$, when holding the true $q_{j}$ fixed at $0.9$. We performed $10,000$
iterations where cost-aware $\alpha$-investing is restricted to a single
sample and $a=1$.

| Tests | True Rejects | False Rejects | mFDR
---|---|---|---|---
Specified q |  |  |  |
0.50 | 2.7 | 0.13 | 0.06 | 0.049
0.70 | 10.6 | 0.33 | 0.06 | 0.047
0.80 | 32.9 | 0.72 | 0.08 | 0.047
0.85 | 92.4 | 1.58 | 0.13 | 0.049
0.89 | 282.4 | 3.54 | 0.20 | 0.044
0.90 | 365.0 | 4.15 | 0.22 | 0.041
Table 6: Varying the magnitude of misspecification of $q_{j}$ shows that small
deviations from the true value do not dramatically change performance,
however, larger misspecifications result in fewer tests performed and fewer
rejections. However, mFDR is still controlled.

When $q_{j}$ is fixed, the optimal sample size displays a peak. Empirically,
it seems that when the probability of the null is large, but not too large,
cost-aware ERO finds it advantageous to commit a large amount of samples
because the $\alpha$-reward is high if rejection is successful.

Figure 5: Optimal Sample size for varying levels of the prior of the null
hypothesis. Here we initialize $\rho_{j}=1$, set $W_{\alpha}=0.0475$, and do
not set an upper bound for $n_{j}$.

##  Appendix F COMPARISON WITH OTHER METHODS WITH $n_{j}=10$

The simulation study used in Table 2 was repeated with setting $n=10$ for the
existing methods and $n_{j}\leq 10$ for cost-aware ERO. The cost per sample
was set to $c_{j}=1$, and the total budget was $W_{\$}[0]=1000$. Hence, for
methods that do not optimize sample size, the number of tests was limited to
$100$.

Cost-aware ERO performs more tests and rejects more true alternative
hypotheses than existing methods. These results demostrate that even when
state-of-the-art methods have access to larger sample sizes, the ability to
optimize the sample size results in better performance.

|  | Tests | True Rejects | False Rejects | mFDR
---|---|---|---|---|---
Scheme | Method |  |  |  |
constant | spending | 10.0 | 1.00 | 0.05 | 0.02
| investing | 54.0 | 5.40 | 0.23 | 0.035
| rewards k = 1 | 47.8 | 4.79 | 0.20 | 0.034
| rewards k = 1.1 | 49.1 | 4.91 | 0.19 | 0.031
| ERO investing | 54.0 | 5.40 | 0.23 | 0.035
relative | spending | 66.0 | 6.55 | 0.05 | 0.006
| investing | 99.9 | 10.00 | 0.52 | 0.045
| rewards k = 1 | 99.9 | 10.00 | 0.45 | 0.039
| rewards k = 1.1 | 99.9 | 10.00 | 0.40 | 0.036
| ERO investing | 99.9 | 10.00 | 0.52 | 0.045
other | LORD++ | 98.0 | 9.80 | 0.12 | 0.011
| LORD1 | 100.0 | 9.99 | 0.07 | 0.006
| LORD2 | 100.0 | 10.00 | 0.16 | 0.014
| LORD3 | 100.0 | 10.00 | 0.16 | 0.014
| saffron | 100.0 | 10.00 | 0.44 | 0.038
Table 7: Using a non-optimized pure strategy of setting n=10 (max n
permissible in cost-aware simulations in Table 2). Although using a larger
number of samples for each test gives more powerful tests, the number of
samples used by cost-aware ERO investing is lower than all methods other than
a constant spending scheme for $\alpha$-spending, which only gives a single
true rejection.

##  Appendix G TWO-STEP COST AWARE ERO INVESTING

In order to set nature’s strategy to equalizing in the two-step optimal
procedure, the expected change in $\alpha$-wealth must be equal no matter what
strategy the experimenter uses. It follows that the expected change in
$\alpha$-wealth must be found for each strategy, and the system of equations
solved.

In order for the martingale solution for the two-step game to hold, the
following equations must hold.

$0=P(TT_{1})(-\varphi_{1}-\varphi_{2}+\alpha_{1}\psi_{1}+\alpha_{2}\psi_{2})+P(TT_{2})(-\varphi_{1}-\varphi_{2}+\alpha_{1}\psi_{1}+\rho_{2}\psi_{2})\\\
+P(TT_{3})(-\varphi_{1}-\varphi_{2}+\rho_{1}\psi_{1}+\alpha_{2}\psi_{2})+P(TT_{4})(-\varphi_{1}-\varphi_{2}+\rho_{1}\psi_{1}+\rho_{2}\psi_{2})$
(42)
$0=P(TS_{1})(-\varphi_{1}+\alpha_{1}\psi_{1})+P(TS_{2})(-\varphi_{1}+\rho_{1}\psi_{1})$
(43)
$0=P(ST_{1})(-\varphi_{2}+\alpha_{2}\psi_{2})+P(ST_{2})(-\varphi_{2}+\rho_{2}\psi_{2}),$
(44)

where

$P(TT_{1})=(q_{1})(q_{2})$ (45) $P(TT_{2})=(q_{1})(1-q_{2})$ (46)
$P(TT_{3})=(1-q_{1})(q_{2})$ (47) $P(TT_{4})=(1-q_{1})(1-q_{2})$ (48)
$P(TS_{1})=q_{1}$ (49) $P(TS_{2})=1-q_{1}$ (50) $P(ST_{1})=q_{2}$ (51)
$P(ST_{2})=1-q_{2}$ (52)

Selecting the optimal sample size of one step versus two steps reveals that
knowledge of future tests inherently limits the number of samples allocated on
a single test. We can see that the knowledge of the second test greatly
reduces the desire to risk such high levels of $\alpha$ and dollar wealth. We
do note, for certain combinations of $q_{1}$ and $q_{2}$, although rare, the
optimized $n_{1}$ and $n_{2}$ seem to converge to large values and this may be
due to the nonlinear solver.

$q_{1}$/$q_{2}$ | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9
---|---|---|---|---|---|---|---|---|---
0.1 | 0.588 | 0.588 | 0.595 | 0.592 | 0.586 | 0.458 | 0.532 | 0.765 | 0.352
0.2 | 0.608 | 0.588 | 0.594 | 0.586 | 0.586 | 0.587 | 0.485 | 0.767 | 0.351
0.3 | 0.591 | 0.588 | 0.588 | 0.585 | 0.593 | 0.586 | 0.484 | 1.603 | 0.434
0.4 | 0.851 | 0.851 | 0.851 | 0.851 | 0.851 | 0.851 | 0.851 | 1.613 | 0.851
0.5 | 1.895 | 1.895 | 1.895 | 1.895 | 1.895 | 1.895 | 1.895 | 1.895 | 1.895
0.6 | 553.624 | 552.578 | 550.467 | 13.314 | 3264.044 | 12.280 | 12.383 | 12.107 | 12.790
0.7 | 518.789 | 514.956 | 1303.099 | 29.686 | 13.409 | 12.350 | 12.536 | 12.510 | 13.653
0.8 | 15.839 | 14.104 | 14.321 | 12.650 | 12.650 | 12.962 | 12.473 | 12.530 | 13.660
0.9 | 49.216 | 13.400 | 49.334 | 13.404 | 13.612 | 13.038 | 12.958 | 12.969 | 13.498
Table 8: Values for optimal sample size of test 1, for unlimited $W_{\$}$ and $W_{\alpha}$ = 0.0475 $q_{1}$/$q_{2}$ | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9
---|---|---|---|---|---|---|---|---|---
0.1 | 0.473 | 0.473 | 0.434 | 0.851 | 1.895 | 522.703 | 12.334 | 14.206 | 13.456
0.2 | 0.582 | 0.473 | 0.434 | 0.851 | 1.895 | 12.704 | 13.577 | 14.201 | 13.452
0.3 | 0.595 | 0.473 | 0.474 | 0.851 | 1.895 | 13.037 | 13.584 | 20.383 | 13.386
0.4 | 0.589 | 0.591 | 0.434 | 0.851 | 1.895 | 12.225 | 12.700 | 48593.014 | 13.365
0.5 | 0.554 | 0.556 | 0.434 | 0.851 | 1.895 | 11.828 | 12.252 | 20.707 | 12.913
0.6 | 0.506 | 0.506 | 0.506 | 0.851 | 1.895 | 12.271 | 12.723 | 12.815 | 13.400
0.7 | 0.528 | 0.526 | 0.543 | 0.851 | 1.895 | 11.963 | 12.462 | 12.738 | 13.428
0.8 | 0.487 | 0.466 | 0.465 | 0.851 | 1.895 | 12.379 | 12.653 | 12.526 | 13.087
0.9 | 0.508 | 0.508 | 0.507 | 0.851 | 1.895 | 12.092 | 12.964 | 15.516 | 16.036
Table 9: Values for optimal sample size of test 2, for unlimited $W_{\$}$ and
$W_{\alpha}$ = 0.0475