# An Adaptive-Discard-Graph for online error control

Lasse Fischer
Competence Center for Clinical Trials Bremen
University of Bremen
<EMAIL_ADDRESS>
&Marta Bofill Roig
Center for Medical Data Science
Medical University of Vienna
<EMAIL_ADDRESS>
&Werner Brannath
Competence Center for Clinical Trials Bremen
University of Bremen
<EMAIL_ADDRESS>

###### Abstract

In recent years, graphical multiple testing procedures have gained popularity
due to their generality and ease of interpretation. In contemporary research,
online error control is often required, where an error criterion, such as
familywise error rate (FWER) or false discovery rate (FDR), shall remain under
control while testing an a priori unbounded sequence of hypotheses. Although
the classical graphical procedure can be extended to the online setting,
previous work has shown that it leads to low power, and other approaches, such
as Adaptive-Discard (ADDIS) procedures, are preferred instead. In this paper,
we introduce an ADDIS-Graph with FWER control and its extension for the FDR
setting. These graphical ADDIS procedures combine the good interpretability of
graphical procedures with the high online power of ADDIS procedures. Moreover,
they can be adapted to a local dependence structure and an asynchronous
testing setup, leading to power improvements over the current state-of-art
methods. Consequently, the proposed methods are useful for a wide range of
applications, including innovative complex trial designs, such as platform
trials, and large-scale test designs, such as in the evaluation of A/B tests
for marketing research.

_K_ eywords graphical testing procedures $\cdot$ false discovery rate $\cdot$
familywise error rate $\cdot$ online multiple testing.

##  1 Introduction

In online multiple testing, an infinite stream of hypotheses
$(H_{i})_{i\in\mathbb{N}}$ is tested sequentially (Foster and Stine,, 2008).
This means, at each step $i\in\mathbb{N}$, a decision has to be made on the
current hypothesis $H_{i}$ while having access only to the previous hypotheses
and decisions. Since the number of hypotheses to be tested in the future is
unknown, an infinite number is usually assumed. Due to the testing of multiple
hypotheses, the probability of making false discoveries increases and a
multiplicity correction is required. Usually, either the familywise error rate
(FWER) or the false discovery rate (FDR) are used as error criteria. While
controlling the FWER refers to maintaining the probability of rejecting at
least one true null hypothesis below some pre-specified threshold, the FDR
controls the expected proportion of true hypotheses among the rejections, and
thus allows making false discoveries (Benjamini and Hochberg,, 1995). The
choice of error criterion depends on the study and the associated stringency
towards false rejections. In some online applications, the less conservative
FDR is preferred, as the number of hypotheses is very large. Examples can be
found in the marketing of large internet companies, which conduct a sequence
of so-called A/B tests to improve websites (Kohavi et al.,, 2013). However,
there are also applications where false discoveries need to be avoided and
control of the FWER is necessary. For instance, specific platform trials can
be embedded in the online multiple testing setting (Robertson et al., 2022a, )
and in such clinical trials FWER control may be required. In genetic studies,
an a priori unbounded sequence of hypotheses is tested (Muñoz-Fuentes et al.,,
2018), often with an interest in the FWER. Another example where online FWER
is essential is the updating of a machine learning algorithm (Feng et al.,,
2022).

In classical “offline” multiple testing, graphical approaches have been
suggested to facilitate the visualization and communication of multiple
testing procedures. In the seminal paper, Bretz et al., (2009) proposed the
representation of multiple testing procedures by directed graphs, where the
null hypotheses are represented by nodes accompanied by their initial
significance levels and connected by weighted vertices, illustrating error
propagation if the hypotheses are rejected. The graphical procedures provide
FWER control, facilitate the illustration of the study objectives and are very
popular as many test procedures can be represented by this graphical structure
(Bretz et al.,, 2009). The graphical approaches were later extended to
adaptive designs (Klinglmueller et al.,, 2014) and to other error measures
(Robertson et al.,, 2020), and more recently Tian and Ramdas, (2021) extended
the graphical approach to the online case. Fischer et al., (2022) presented a
new online closure principle which ensures that the resulting closed procedure
can be applied in the online setting and, in particular, showed how the online
version of the graphical procedure can be written as an online closed
procedure based on the Alpha-Spending (Foster and Stine,, 2008). Feng et al.,
(2022) also used an online version of the graphical procedure for a specific
online multiple testing problem, namely, the updating of a machine learning
algorithm. In addition, they included the correlation structure between the
$p$-values in order to improve the algorithm. However, one disadvantage the
previously mentioned online graphical approaches have in common is that the
individual significance levels are typically rather low due to a large number
of hypotheses in online multiple testing. Since the significance level is only
distributed to the future hypotheses when a $p$-value is below an individual
significance level, an update of the levels is unlikely, which results in low
power. A more promising approach to online FWER control is the Adaptive-
Discard (ADDIS) principle by Tian and Ramdas, (2021). It allows to preserve
the individual significance level of a hypothesis $H_{i}$ for the future
testing process if the $p$-value $P_{i}$ lies outside of an interval
$(\lambda_{i},\tau_{i}]$ with $0\leq\lambda_{i}<\tau_{i}\leq 1$. Tian and
Ramdas, (2021) proposed the ADDIS-Spending as a concrete ADDIS procedure. In
the case of $P_{i}\leq\lambda_{i}$ or $P_{i}>\tau_{i}$, the ADDIS-Spending
ignores the hypothesis $H_{i}$ in the future testing process and adjusts the
future significance levels accordingly. The price for this improvement is a
testing factor $(\tau_{i}-\lambda_{i})$, which needs to be multiplied by the
individual significance level before comparing it with the $p$-value. In
comparison to FWER, a variety of approaches have been proposed for FDR control
(Foster and Stine,, 2008; Ramdas et al.,, 2017, 2018; Javanmard and
Montanari,, 2018; Tian and Ramdas,, 2019). Also, in this case, the
$\text{ADDIS}^{*}$ procedure proposed by Tian and Ramdas, (2019), which is
based on an ADDIS principle for FDR control, seems to be the most promising in
terms of online power (Robertson et al., 2022b, ). However, ADDIS-Spending and
$\text{ADDIS}^{*}$ lack generality and interpretability, which also leads to
power loss in certain frameworks, such as local dependency and an asynchronous
test structure. Our main contribution in this paper is the so-called ADDIS-
Graph. The ADDIS-Graph allows to distribute significance level to future
hypotheses whenever a $p$-value $P_{i}$ is less or equal than $\lambda_{i}$ or
greater than $\tau_{i}$. Consequently, the ADDIS-Graph combines the good
interpretability of graphical procedures with the high online power of ADDIS
procedures.

In Section 2, we formally describe the setting and present the online version
of the graphical procedure, the ADDIS principle for FWER control and the
ADDIS-Spending (Tian and Ramdas,, 2021). Based on these concepts, we derive
the ADDIS-Graph for FWER control and show that it contains all other online
procedures satisfying the ADDIS principle (Section 3). The visual
representation of the ADDIS-Graph clarifies the dependencies between an
individual significance level and the outcomes of previous tests. This allows
the ADDIS-Graph to adapt to complex situations, resulting in high efficiency.
We illustrate this by showing that the ADDIS-Graph leads to an improvement
over the ADDIS-Spending under local dependence (Section 4). In Section 5, we
transfer the ADDIS-Graph approach to the FDR setting, resulting in the FDR-
ADDIS-Graph. Here, we show superiority over $\text{ADDIS}^{*}$ with the
example of an asynchronous testing setup, where a test does not necessarily
start and finish at the same step. In Sections 6 and 7, we compare our
proposals with the procedures proposed by Tian and Ramdas, (2019, 2021)
through a simulation study and application to real data, respectively. All
formal proofs of the theoretical assertions are in the Appendix.

##  2 Preliminaries

###  2.1 Setting and notation

Let $I_{0}$ be the index set of true hypotheses, $R(i)$ be the index set of
rejected hypotheses up to step $i\in\mathbb{N}$ and $V(i)=I_{0}\cap R(i)$
denote the index set of falsely rejected hypotheses up to step $i$. We aim to
control the familywise error rate

$\displaystyle\text{FWER}(i)\coloneqq\mathbb{P}(|V(i)|>0)$ (1)

at each step $i\in\mathbb{N}$, where $\mathbb{P}$ denotes the probability
under the true configuration of true and false hypotheses. Since
$\text{FWER}(i)$ is nondecreasing, it is sufficient to control
$\text{FWER}\coloneqq\mathbb{P}(v>0)$, where
$v\coloneqq\lim\limits_{i\to\infty}|V(i)|$. The FWER is controlled strongly at
level $\alpha$, if $\text{FWER}\leq\alpha$ for any configuration of true and
false null hypotheses. In contrast, weak control only provides that
$\text{FWER}\leq\alpha$ under the global null hypothesis, which assumes that
all hypotheses are true ($I_{0}=\mathbb{N}$). In this paper, we focus on
strong control.

Denoting by $(P_{i})_{i\in\mathbb{N}}$ the $p$-values corresponding to the
hypotheses $(H_{i})_{i\in\mathbb{N}}$. Each null $p$-value $P_{i}$, $i\in
I_{0}$, is assumed to be valid, meaning $\mathbb{P}(P_{i}\leq x)\leq x$ for
all $x\in[0,1]$. A hypothesis $H_{i}$ is rejected, if $P_{i}\leq\alpha_{i}$,
where $\alpha_{i}\in[0,1)$ is the individual significance level of $H_{i}$.
ADDIS algorithms also require additional parameters
$(\tau_{i})_{i\in\mathbb{N}}$ and $(\lambda_{i})_{i\in\mathbb{N}}$ with values
in $(0,1]$ and $[0,\tau_{i})$, respectively. In order to apply a multiple
testing procedure in the online setting, these parameters are only allowed to
depend on information about previous $p$-values. Mathematically,
$(\alpha_{i})_{i\in\mathbb{N}}$, $(\tau_{i})_{i\in\mathbb{N}}$ and
$(\lambda_{i})_{i\in\mathbb{N}}$ are sequences of random variables such that
$\alpha_{i}$, $\tau_{i}$ and $\lambda_{i}$ are measurable with respect to
$\mathcal{G}_{i-1}\coloneqq\sigma(\\{R_{1},S_{1},C_{1},\ldots,R_{i-1},S_{i-1},C_{i-1}\\})$,
where $R_{j}=\mathbbm{1}_{P_{j}\leq\alpha_{j}}$,
$S_{j}=\mathbbm{1}_{P_{j}\leq\tau_{j}}$ and
$C_{j}=\mathbbm{1}_{P_{j}\leq\lambda_{j}}$.

###  2.2 Online-Graph and ADDIS procedures

In the following, we present essential concepts for constructing an ADDIS-
Graph. We start with the Online-Graph, which was introduced by Tian and
Ramdas, (2021) (named Online-Fallback procedure in their paper) as the online
version of the graphical procedure by Bretz et al., (2009). Fischer et al.,
(2022) have shown how the Online-Graph can be obtained by the online closure
principle. Afterwards, we present the ADDIS principle and ADDIS-Spending by
Tian and Ramdas, (2021).

The procedures considered in this paper involve a non-negative sequence
$(\gamma_{i})_{i\in\mathbb{N}}$ with $\sum_{i\in\mathbb{N}}\gamma_{i}\leq 1$,
which can be interpreted as the initial allocation of the significance level
$\alpha$. The graphical procedures additionally require non-negative weights
$(g_{j,i})_{i=j+1}^{\infty}$ for all $j\in\mathbb{N}$ with
$\sum_{i=j+1}^{\infty}g_{j,i}\leq 1$, which determine the updating of the
individual significance levels during the testing process. With this, the
Online-Graph is defined as

$\displaystyle\alpha_{i}=\alpha\gamma_{i}+\sum_{j=1}^{i-1}g_{j,i}R_{j}\alpha_{j}.$
(2)

The Online-Graph is illustrated in Figure 1. The initial individual
significance level is below each hypothesis. After the rejection of a
hypothesis $H_{j}$, $j\in\mathbb{N}$, the individual significance level of
$H_{j}$ is distributed to the future hypotheses according to the weights
$(g_{j,i})_{i=j+1}^{\infty}$. The rectangles below the nodes can be ignored
for the Online-Graph and the dots at the end refer to the fact that there is
an infinite number of future hypotheses.

Due to the ease of interpretation, graphical multiple testing procedures are
very popular. However, except for unrealistic extreme cases (e.g. that each
hypothesis can be rejected), the individual significance levels
$(\alpha_{i})_{i\in\mathbb{N}}$ of the Online-Graph tend to $0$ for $i$ to
infinity. This means that the probability of distributing a significance level
to the future hypotheses becomes enormously unlikely at a late stage of the
testing process, which results in low power. For this reason, Tian and Ramdas,
(2021) have proposed an ADDIS principle that preserves the significance level
of $H_{i}$ for the future testing process, if $P_{i}\leq\lambda_{i}$ or
$P_{i}>\tau_{i}$. In this way, the decrease of the significance levels can be
slowed down and thus the power increased. However, this improvement also has
its cost. In order to control the FWER, it is required that the null
$p$-values are independent of each other and the non-nulls. In addition, it is
assumed that the null $p$-values are uniformly valid, which means
$\mathbb{P}(P_{i}\leq xy|P_{i}\leq y)\leq x$ for all $x,y\in[0,1]$ and $i\in
I_{0}$ (Zhao et al.,, 2019). Furthermore, in case of
$\lambda_{i}<P_{i}\leq\tau_{i}$, the level $\alpha_{i}/(\tau_{i}-\lambda_{i})$
is lost instead of just $\alpha_{i}$.

######  Theorem 2.1 (ADDIS principle for FWER control (Tian and Ramdas,,
2021)).

Assume the null $p$-values are uniformly valid and independent from each other
and the non-nulls. Every multiple testing procedure controls the FWER in the
strong sense when the individual significance levels
$(\alpha_{i})_{i\in\mathbb{N}}$ satisfy

$\displaystyle\sum_{j=1}^{i}\frac{\alpha_{j}}{\tau_{j}-\lambda_{j}}(S_{j}-C_{j})\leq\alpha\quad\text{for
all }i\in\mathbb{N}.$ (3)

The ADDIS principle combines the two concepts of adaptivity and discarding.
The idea of adaptivity is based on the fact that false hypotheses cannot lead
to a type I error and thus testing false hypotheses does not increase the
FWER. Hence, $\lambda_{i}$ is used to estimate whether a hypothesis is true or
false. The discarding approach uses the fact that null $p$-values are often
conservative, meaning $\mathbb{P}(P_{i}\leq x)<x$ or equivalently
$\mathbb{P}(P_{i}>x)>1-x$ for some $x\in[0,1]$ and $i\in I_{0}$. Discarding
exploits this by accepting large $p$-values without testing, which leads to
higher significance levels for the remaining hypotheses. Note that one could
also consider the adaptivity and discarding part separately by setting
$\tau_{i}=1$ or $\lambda_{i}=0$ respectively for all $i\in\mathbb{N}$. In case
of $\tau_{i}=1$, the assumption about the null $p$-values being uniformly
valid can be dropped (Tian and Ramdas,, 2021).

Online multiple testing procedures that follow Theorem 2.1 are called ADDIS
procedures. As a concrete ADDIS procedure, Tian and Ramdas, (2021) proposed
the ADDIS-Spending. The idea of ADDIS-Spending is to ignore a hypothesis
$H_{i}$ in case of $P_{i}\leq\lambda_{i}$ or $P_{i}>\tau_{i}$ in the future
testing process and adjust the significance levels accordingly. This results
in the individual significance level

$\displaystyle\alpha_{i}=\alpha(\tau_{i}-\lambda_{i})\gamma_{t(i)},\quad\text{where
}t(i)=1+\sum_{j=1}^{i-1}(S_{j}-C_{j}).$ (4)

##  3 ADDIS-Graph for FWER control

Tian and Ramdas, (2021) showed by means of simulations that the ADDIS-Spending
(in equation (4)) leads to a substantially higher power than the one achieved
when using the Online-Graph. However, the interpretation of the Online-Graph
is easier, which makes it simpler to use. To this end, we bring together the
approaches of the Online-Graph (in (2)) and the ADDIS principle (Theorem 2.1),
resulting in what we call the ADDIS-Graph.

######  Definition 3.1 (ADDIS-Graph).

Let $(\gamma_{i})_{i\in\mathbb{N}}$ and $(g_{j,i})_{i=j+1}^{\infty}$,
$j\in\mathbb{N}$, be non-negative sequences that sum to at most one. In
addition, let $\tau_{i}\in(0,1]$ and $\lambda_{i}\in[0,\tau_{i})$ be
measurable regarding $\mathcal{G}_{i-1}$ for all $i\in\mathbb{N}$. The ADDIS-
Graph tests each hypothesis $H_{i}$ at significance level

$\displaystyle\alpha_{i}=(\tau_{i}-\lambda_{i})\left(\alpha\gamma_{i}+\sum_{j=1}^{i-1}g_{j,i}(C_{j}-S_{j}+1)\frac{\alpha_{j}}{\tau_{j}-\lambda_{j}}\right).$
(5)

######  Theorem 3.2.

The ADDIS-Graph satisfies the ADDIS principle (Definition 2.1) and thus
controls the FWER in the strong sense when the the null $p$-values are
uniformly valid and independent from each other and the non-nulls.

In order to represent this ADDIS-Graph as a graph, consider
$\tilde{\alpha}_{i}=\alpha_{i}\frac{1}{\tau_{i}-\lambda_{i}}$ for all
$i\in\mathbb{N}$, where $\alpha_{i}$ is the significance level obtained by the
ADDIS-Graph. Equation (5) gives us
$\tilde{\alpha}_{i}=\alpha_{i}\frac{1}{\tau_{i}-\lambda_{i}}=\alpha\gamma_{i}+\sum_{j=1}^{i-1}g_{j,i}(C_{j}-S_{j}+1)\tilde{\alpha}_{j}$.
Comparing this with the Online-Graph (2), the
$(\tilde{\alpha}_{i})_{i\in\mathbb{N}}$ can be interpreted as the significance
levels we would obtain by a graph with initial levels
$(\alpha\gamma_{i})_{i\in\mathbb{N}}$ that updates the future levels whenever
a $p$-value $P_{j}$, $j\in\mathbb{N}$, is less or equal than $\lambda_{j}$ or
greater than $\tau_{j}$. Thus, one can first determine $\tilde{\alpha}_{i}$
using this graph and then compute the level of the ADDIS-Graph as
$\alpha_{i}=\tilde{\alpha}_{i}(\tau_{i}-\lambda_{i})$. This fact is used to
illustrate the ADDIS-Graph in Figure 1. It can be interpreted just as the
Online-Graph, with two subtle differences. First, we can choose at each step
$j\in\mathbb{N}$ limits $\tau_{j}\in[0,1)$ and $\lambda_{j}\in(0,\tau_{j}]$
for the $p$-value $P_{j}$ that determine when the significance level of the
$j$-th hypothesis is distributed among the future hypotheses. Second, we need
to include an additional testing factor based on these parameters, which is
illustrated in the rectangle below each hypothesis. This testing factor is
only multiplied with the individual significance level when the corresponding
hypothesis is tested, but it is not involved in the updating process with the
graph.

Figure 1: Illustration of the ADDIS-Graph. Ignoring the rectangles the figure
can also be interpreted as the Online-Graph.

When defining the ADDIS-Graph, we considered the parameters
$(\gamma_{i})_{i\in\mathbb{N}}$ and $(g_{j,i})_{i=j+1}^{\infty}$,
$j\in\mathbb{N}$ as fixed. However, we do not need this assumption to satisfy
the conditions of Theorem 2.1 and thus to control the FWER. Consequently,
$\gamma_{i}$ and $g_{j,i}$ could also be random variables that are measurable
regarding $\mathcal{G}_{i-1}$. With this, the procedures become more flexible.
It can even be shown that, in this case, the ADDIS-Graph is the general ADDIS
procedure, thus containing all procedures satisfying the ADDIS principle
(Theorem 2.1).

######  Theorem 3.3.

Let $\gamma_{i}$ ($i\in\mathbb{N}$) and $g_{j,i}$ ($j\in\mathbb{N}$, $i>j$) be
measurable with respect to $\mathcal{G}_{i-1}$. Then, any procedure satisfying
the ADDIS principle (Theorem 2.1) can be written as an ADDIS-Graph (Definition
3.1).

Note that the ADDIS-Graph is more general than the ADDIS-Spending, as Theorem
3.3 does not hold for ADDIS-Spending. To see this, suppose we choose a fix
$\lambda_{i}=\lambda$ and $\tau_{i}=\tau$ for all $i\in\mathbb{N}$. Then
$P_{i}\leq\lambda$ or $P_{i}>\tau$ directly implies $\alpha_{i}=\alpha_{i+1}$
(see (4)) which does not need to hold for every other ADDIS procedure.

######  Remark.

For a positive and nonincreasing $(\gamma_{i})_{i\in\mathbb{N}}$, one could
write the ADDIS-Spending as an ADDIS-Graph by choosing
$g_{j,i}=(\gamma_{t(j)+i-j-1}-\gamma_{t(j)+i-j})/\gamma_{t(j)}$, where
$t(j)=1+\sum_{k=1}^{j-1}(S_{k}-C_{k})$. If $(\gamma_{i})_{i\in\mathbb{N}}$ is
increasing, it becomes more complex, as the $(\gamma_{i})_{i\in\mathbb{N}}$
used in the ADDIS-Graph would need an adjustment as well.

For the sake of simplicity, we consider $(\gamma_{i})_{i\in\mathbb{N}}$ and
$(g_{j,i})_{j\in\mathbb{N},i>j}$ as fixed parameters in the remainder of this
paper. In the following section, we show that the ADDIS-Graph can handle local
dependence structures and argue why it provides a major improvement over the
ADDIS-Spending under local dependence.

##  4 ADDIS-Graph under local dependence

Procedures based on the ADDIS principle (Theorem 2.1) only control the FWER
when the $p$-values are independent. In practice, this assumption is often
violated. For example, when the same control group is used to test
experimental groups in different hypotheses or the formulation of new
hypotheses is based on the previous test outcomes. On the other hand, it is
unlikely that $p$-values from the distant past have any influence on the
current testing, as the data and context of the data might have changed. For
this reason, Zrnic et al., (2021) have proposed a local dependence structure.
Assume that a fixed sequence of lags $(L_{i})_{i\in\mathbb{N}}$ with
$L_{i}\in\\{0,1,\ldots,i-1\\}$ and $L_{i+1}\leq L_{i}+1$ for all
$i\in\mathbb{N}$ is given. Then, the $p$-values $(P_{i})_{i\in\mathbb{N}}$ are
called locally dependent, if $\forall i\in\mathbb{N}$ holds:

$P_{i}\perp P_{i-L_{i}-1},P_{i-L_{i}-2},\ldots,P_{1}.$

For every $P_{i}$, this local dependency structure specifies up to which point
of time the previous p-values are independent of $P_{i}$. Note that local
dependence contains independence ($L_{i}=0$ $\forall i\in\mathbb{N}$) and
arbitrary dependence ($L_{i}=i-1$ $\forall i\in\mathbb{N}$) as special cases.
Although we consider the lags as fixed, they do not need to be known before
the evaluation. However, $L_{i}$ has to be determined at the beginning of step
$i\in\mathbb{N}$ and must not depend on the data itself. For example, the lags
could be based on content-related information about the data. Tian and Ramdas,
(2021) showed that local dependence can be incorporated into the ADDIS
principle (Theorem 2.1) by ignoring the dependent $p$-values and making
pessimistic assumptions instead. Mathematically, $\alpha_{i}$, $\lambda_{i}$
and $\tau_{i}$ need to be measurable regarding
$\mathcal{G}_{i-L_{i}-1}=\sigma(\\{P_{1},\ldots,P_{i-L_{i}-1}\\})$. Tian and
Ramdas, (2021) used this to adjust their ADDIS-Spending (4) to the local
dependence by requiring $(\gamma_{i})_{i\in\mathbb{N}}$ to be nonincreasing
and setting

$\displaystyle\alpha_{i}=\alpha(\tau_{i}-\lambda_{i})\gamma_{t(i)},\quad\text{where
}t(i)=1+L_{i}+\sum_{j=1}^{i-L_{i}-1}(S_{j}-C_{j}).$ (6)

Note that this procedure, which we refer to as $\textit{ADDIS-
Spending}_{\textit{local}}$, loses significance level due to local dependence.
To see that, suppose
$\alpha_{i}^{*}=\alpha(\tau_{i}-\lambda_{i})\gamma_{t^{*}(i)}$, where
$t^{*}(i)=1+\sum_{j=1}^{i-1}(S_{j}-C_{j})$. Then, $\alpha_{i}^{*}$ can be
interpreted as the level we would obtain under independence ($L_{i}=0$). It is
easy to see that $t^{*}(i)\leq t(i)$, and often even strictly smaller. For
example, suppose $P_{1}$ and $P_{2}$ depend on each other $(L_{2}=1)$. If
$P_{1}\leq\lambda_{1}$ or $P_{1}>\tau_{1}$, we have $t^{*}(2)=1<2=t(2)$ and if
additionally $\gamma_{1}>\gamma_{2}$, we also have
$\alpha_{2}^{*}>\alpha_{2}$. Since $(\gamma_{i})_{i\in\mathbb{N}}$ needs to be
decreasing at some steps (unless it is constant $0$) and often is at every
step, the power loss is inevitable and can get high when the lags
$(L_{i})_{i\in\mathbb{N}}$ are large. In the following, we will see that this
power loss can be avoided using the ADDIS-Graph.

First, we adjust the ADDIS-Graph to the local dependence structure such that
FWER control is preserved. After that, we show how the weights of the ADDIS-
Graph can be used such that no significance level is lost. A simple way to
account for local dependence in the ADDIS-Graph (Figure 1) is to remove the
arrows connecting dependent $p$-values and adjust the individual significance
levels of the ADDIS-Graph (Definition 3.1) to

$\displaystyle\alpha_{i}=(\tau_{i}-\lambda_{i})\left(\alpha\gamma_{i}+\sum_{j=1}^{i-L_{i}-1}g_{j,i}(C_{j}-S_{j}+1)\frac{\alpha_{j}}{\tau_{j}-\lambda_{j}}\right).$

In Figure 2, the ADDIS-Graph is illustrated for a specific local dependence
structure. In this example, $L_{2}=1$, meaning $P_{1}$ and $P_{2}$ depend on
each other. This is illustrated by the dotted line. Hence, the link $g_{1,2}$
is removed as no significance level of the first hypothesis can be allocated
to the second. Furthermore, $L_{3}$ was chosen equal to zero, which is why no
further adjustment of the graph was needed. Note that by removing the weight
$g_{1,2}$ potential significance level is lost as well as in ADDIS-Spending.
However, the ADDIS-Graph allows to adjust the weights to the given local
dependence structure. For example, by adding $g_{1,2}$ to one of the other
weights $g_{1,i}$, $i>2$. In that case, it may be that not the same hypotheses
benefit from the first hypothesis, but the same amount of significance level
is distributed as under independence.

Figure 2: Adjustment of the ADDIS-Graph (Figure 1) to a local dependence
structure in which $P_{1}$ and $P_{2}$ depend on each other.

In order to formalise such strategies, note that $L_{i+1}\leq L_{i}+1$ for all
$i\in\mathbb{N}$ implies that $i-L_{i}$ is nondecreasing in $i$. Hence, if we
define $d_{j}\coloneqq\min\\{i\in\mathbb{N}:i-L_{i}>j\\}$ (we set
$\min(\emptyset)=\infty$) as the index of the first future $p$-value that does
not depend on $P_{j}$, all $P_{k}$ with $k>d_{j}$ are independent from $P_{j}$
as well. Thus, the idea is to distribute the entire significance level of
$H_{j}$ in case of $P_{j}\leq\lambda_{j}$ or $P_{j}>\tau_{j}$ only to
hypotheses $H_{k}$ with $k\geq d_{j}$. For this, we propose to remove the
weights between dependent hypotheses and standardise the remaining weights,
which leads to the following ADDIS-Graph under local dependence.

######  Definition 4.1 ($\text{ADDIS-Graph}_{\text{local}}$).

Assume local dependence with the lags $(L_{i})_{i\in\mathbb{N}}$. Let
$(\gamma_{i})_{i\in\mathbb{N}}$ be a non-negative sequence that sums up to $1$
and $(g_{j,i})_{i=j+1}^{\infty}$ be a non-negative sequence for all
$j\in\mathbb{N}$ such that $\sum_{i=j+1}^{k}g_{j,i}<1$ for all $k>j$. In
addition, let $\tau_{i}\in(0,1]$ and $\lambda_{i}\in[0,\tau_{i})$ be
measurable regarding
$\mathcal{G}_{i-L_{i}-1}=\sigma(\\{P_{1},\ldots,P_{i-L_{i}-1}\\})$. The
$\textit{ADDIS-Graph}_{\textit{local}}$ tests each hypothesis $H_{i}$ at
significance level

$\displaystyle\alpha_{i}=(\tau_{i}-\lambda_{i})\left(\alpha\gamma_{i}+\sum_{j=1}^{i-L_{i}-1}g_{j,i}^{*}(C_{j}-S_{j}+1)\frac{\alpha_{j}}{\tau_{j}-\lambda_{j}}\right),$

where
$g_{j,i}^{*}=g_{j,i}\bigg{/}\left(1-\sum_{k=j+1}^{d_{j}-1}g_{j,k}\right)$ if
$i\geq d_{j}$ and $g_{j,i}^{*}=0$ otherwise.

The FWER control of the $\text{ADDIS-Graph}_{\text{local}}$ comes directly by
Theorem 3.2 and the ADDIS principle under local dependence (Tian and Ramdas,,
2021). Importantly, note that, for all $j\in\mathbb{N}$, it holds

$d_{j}<\infty\text{ and }\sum_{i=j+1}^{\infty}g_{j,i}=1\ \implies\
\sum_{i=j+1}^{\infty}g_{j,i}^{*}=1,$

which implies that there are no uniformly larger weights than
$(g_{j,i}^{*})_{i=j+1}^{\infty}$, that are suitable for an ADDIS-Graph. Since
$\alpha_{i}=\alpha_{i}^{*}\coloneqq(\tau_{i}-\lambda_{i})\left(\alpha\gamma_{i}+\sum_{j=1}^{i-1}g_{j,i}^{*}(C_{j}-S_{j}+1)\alpha_{j}\frac{1}{\tau_{j}-\lambda_{j}}\right)$,
we do not lose significance level compared to the independent case, indicating
superiority over the ADDIS-Spending, where significance level is lost when the
$p$-values are locally dependent.

######  Remark.

1

  * •

The $\text{ADDIS-Graph}_{local}$ does not lose significance due to local
dependence, if $d_{j}<\infty$ for all $j\in\mathbb{N}$, which is equivalent to
$\lim\limits_{i\to\infty}i-L_{i}=\infty$. In particular, this is satisfied if
$(L_{i})_{i\in\mathbb{N}}$ has an upper bound, which indeed covers many cases
that occur in practice. For example, when the hypotheses are tested in finite
batches. That means, there are disjoint groups of $p$-values
$B_{1}=\\{P_{1},\ldots,P_{j}\\}$ ($j\in\mathbb{N}$),
$B_{2}=\\{P_{j},\ldots,P_{k}\\}$ ($k>j$), $B_{3}=\\{P_{k},\ldots,P_{l}\\}$
($l>k$) and so on, such that $p$-values from the same batch may depend on each
other, but hypotheses from different batches are independent.

  * •

There are many other possible ADDIS-Graphs for local dependence. We decided to
present $\text{ADDIS-Graph}_{\text{local}}$ because
$g_{j,i}^{*}/{g_{j,k}^{*}}=g_{j,i}/{g_{j,k}}$ for all $j\in\mathbb{N}$ and
$i,k\geq d_{j}$. Hence, compared to $(g_{j,i})_{i=j+1}^{\infty}$, the weights
$(g_{j,i}^{*})_{i=j+1}^{\infty}$ are increased by the same factor for each
$j\in\mathbb{N}$. Simulations showed that an extremely uneven allocation of
the significance levels leads to low power.

In the same manner as for local dependence, the ADDIS-Graph can be adjusted to
an asynchronous testing setup (Zrnic et al.,, 2021). This is a generalisation
of the online multiple testing framework in which the test for hypothesis
$H_{i}$ is not finished at step $i\in\mathbb{N}$ but at a random time
$E_{i}\geq i$. It is assumed that $E_{i}$ is independent of the $p$-values and
thus can be interpreted as fixed but unknown before time $E_{i}$. One has to
determine a significance level for a hypothesis $H_{j}$ at step
$j\in\mathbb{N}$ without using information about tests that are not finished
before step $j$. Thus, we can adjust the ADDIS-Graph to the asynchronous
setting by removing arrows connecting hypotheses where the testing process
overlaps in time. By standardizing the remaining weights we do not lose any
significance level which again leads to a superiority of the ADDIS-Graph over
the ADDIS-Spending. A more formal construction of an ADDIS-Graph for the
asynchronous setting can be found in the next section, where we derive an
ADDIS-Graph with FDR control.

##  5 ADDIS-Graph for FDR control

In this section, we focus on FDR control, where

$\displaystyle\text{FDR(}i\text{)}\coloneqq\mathbb{E}\left(\frac{|V(i)|}{|R(i)|\lor
1}\right).$ (7)

In order to control FDR($i$) at any time $i\in\mathbb{N}$ using ADDIS
procedures, we need the additional assumptions that
$\lambda_{i}\geq\alpha_{i}$ for all $i\in\mathbb{N}$ and that $\alpha_{i}$,
$\lambda_{i}$ and $1-\tau_{i}$ are monotonic functions of the past. This means
that they are coordinatewise nondecreasing functions in
$R_{1:(i-1)}\coloneqq(R_{1},\ldots,R_{i-1})$ and
$C_{1:(i-1)}\coloneqq(C_{1},\ldots,C_{i-1})$ and nonincreasing in
$S_{1:(i-1)}\coloneqq(S_{1},\ldots,S_{i-1})$. Under these assumptions, Tian
and Ramdas, (2019) showed that the FDR is controlled if the condition of the
ADDIS principle (3) for FWER control (Definition 2.1) is replaced with

$\displaystyle\frac{{}\sum_{j=1}^{i}\frac{\alpha_{j}}{\tau_{j}-\lambda_{j}}(S_{j}-C_{j})}{|R(i)|\lor
1}\leq\alpha\quad\text{for all }i\in\mathbb{N}.$ (8)

######  Remark.

If $\tau_{i}=1$ for all $i\in\mathbb{N}$, the ADDIS principle for FDR control
reduces to the SAFFRON principle by Ramdas et al., (2018). In this case, the
uniformly validity assumption of the null $p$-values can be dropped.

The only difference between the conditions of the ADDIS principle for the FDR
(in (8)) and for the FWER case (in (3)) is the denominator $|R(i)|\lor 1$.
Bringing it on the other side, it can be interpreted as if an additional level
$\alpha$ is gained after each rejection except for the first one. This can be
incorporated into the ADDIS-Graph by distributing an additional $\alpha$ to
future hypotheses in case of rejection according to non-negative weights
$(h_{j,i})_{i=j+1}^{\infty}$ such that $\sum_{i=j+1}^{\infty}h_{j,i}\leq 1$
for all $j\in\mathbb{N}$. For example, one could just choose
$h_{j,i}=g_{j,i}$.

Since no significance level is gained for the first rejection, FDR procedures
often assume that a lower overall significance level of $W_{0}\leq\alpha$ is
available at the beginning of the testing process such that $(\alpha-W_{0})$
can be gained after the first rejection. To differentiate between the first
and other rejections, we additionally define the indicator $T_{i}$ with
$T_{i}=1$, if the first rejection happened within the first $i-1$ steps and
$T_{i}=0$, otherwise. We also set $T_{i}^{c}=1-T_{i}$. With this, the ADDIS-
Graph for FDR control can be defined as follows.

######  Definition 5.1 (FDR-ADDIS-Graph).

Let $(\gamma_{i})_{i\in\mathbb{N}}$, $(g_{j,i})_{j\in\mathbb{N},i>j}$,
$(\tau_{i})_{i\in\mathbb{N}}$ and $(\lambda_{i})_{i\in\mathbb{N}}$ be as in
ADDIS-Graph (Definition 3.1) such that $\tau_{i}$ and $\lambda_{i}$ are
monotonic functions of the past. In addition, let $W_{0}\leq\alpha$ and
$(h_{j,i})_{i=j+1}^{\infty}$, $j\in\mathbb{N}$, be a non-negative sequence
such that $\sum_{i=j+1}^{\infty}h_{i,j}\leq 1$. The FDR-ADDIS-Graph tests each
hypothesis $H_{i}$ at significance level
$\alpha_{i}=\min(\hat{\alpha}_{i},\lambda_{i})$, where

$\displaystyle\hat{\alpha}_{i}=(\tau_{i}-\lambda_{i})\left(W_{0}\gamma_{i}+\sum_{j=1}^{i-1}g_{j,i}(C_{j}-S_{j}+1)\frac{\alpha_{j}}{\tau_{i}-\lambda_{j}}+\sum_{j=1}^{i-1}h_{j,i}R_{j}[\alpha
T_{j}+(\alpha-W_{0})T_{j}^{c}]\right).$ (9)

Obviously, $\alpha_{i}$ is a monotonic function of the past for all
$i\in\mathbb{N}$, which leads to the following conclusion.

######  Theorem 5.2.

The FDR-ADDIS-Graph satisfies equation (8) and thus controls the FDR strongly,
when the null $p$-values are uniformly conservative and independent from each
other and the non-nulls.

The FDR-ADDIS-Graph is illustrated in Figure 3. Note that the figure only
contains $(\hat{\alpha}_{i})_{i\in\mathbb{N}}$ and one needs to set
$\alpha_{i}=\min(\hat{\alpha}_{i},\lambda_{i})$ after using the graph. The
FDR-ADDIS-Graph can be interpreted just as the ADDIS-Graph for FWER control
(Figure 1). The additional grey arrows are activated if the corresponding
hypothesis is rejected. In case of the first rejection, the level $\alpha-
W_{0}$ is distributed to the future hypotheses according to the weights
$(h_{j,i})_{i=j+1}^{\infty}$, $j\in\mathbb{N}$, and in case of any other
rejection, the level $\alpha$ is distributed.

Figure 3: Illustration of the FDR-ADDIS-Graph.

The benefit of the FDR-ADDIS-Graph compared to the proposal of Tian and
Ramdas, (2019), the $\text{ADDIS}^{*}$ algorithm, is similar as for the ADDIS-
Graph for FWER control and the ADDIS-Spending. Due to its graphical structure,
the FDR-ADDIS-Graph is easier to interpret. In particular, the dependencies
between the previous test outcomes and individual significance levels become
clearer.

The FDR-ADDIS-Graph can be easily adapted to an asynchronous setting by
removing the arrows connecting timely overlapping hypotheses. By standardizing
the remaining weights, no significance level is lost, which leads to an
improvement over the $\text{ADDIS}^{*}_{async}$ by Tian and Ramdas, (2019). In
the same way, the FDR-ADDIS-Graph can be adjusted to a local dependence
structure. However, in case of local dependence, only control of the marginal
false discovery rate (mFDR) is provided (Zrnic et al.,, 2021), which is
defined as

$\displaystyle\text{mFDR(}i\text{)}\coloneqq\frac{\mathbb{E}(|V(i)|)}{\mathbb{E}(|R(i)|\lor
1)}.$ (10)

For this reason, we only present an extension of the FDR-ADDIS-Graph to the
asynchronous setting. However, if one is interested in mFDR control under
local dependence, the same adjustments to the FDR-ADDIS-Graph can be made as
we presented in Section 4 for the FWER controlling ADDIS-Graph. To derive an
FDR-ADDIS-Graph for the asynchronous setting, we proceed as described at the
end of Section 4. To this end, let $E_{i}\geq i$, $i\in\mathbb{N}$, be the
stopping times given from the asynchronous testing. The idea is to distribute
the significance level of $H_{j}$ in case of $P_{j}\leq\lambda_{j}$ or
$P_{j}>\tau_{j}$ only to hypotheses $H_{i}$ with $i>E_{j}$, which leads to the
following FDR-ADDIS-Graph for the asynchronous setting.

######  Definition 5.3 ($\text{FDR-ADDIS-Graph}_{\text{async}}$).

Let $W_{0}\leq\alpha$, $(\gamma_{i})_{i\in\mathbb{N}}$ be a non-negative
sequence that sums up to $1$ and $(g_{j,i})_{i=j+1}^{\infty}$ and
$(h_{j,i})_{i=j+1}^{\infty}$ be non-negative sequences for all
$j\in\mathbb{N}$ such that $\sum_{i=j+1}^{k}g_{j,i}<1$ and
$\sum_{i=j+1}^{k}h_{j,i}<1$ for all $k>j$. In addition, let $\tau_{i}\in(0,1]$
and $\lambda_{i}\in[0,\tau_{i})$ be measurable regarding
$\mathcal{G}_{i}^{E}=\sigma(\\{P_{j}:E_{j}<i\\})$. We define
$g_{j,i}^{*}=g_{j,i}\bigg{/}\left(1-\sum_{k=j+1}^{E_{j}}g_{j,k}\right)$,
$h_{j,i}^{*}=h_{j,i}\bigg{/}\left(1-\sum_{k=j+1}^{E_{j}}h_{j,k}\right)$ if
$i>E_{j}$ and $g_{j,i}^{*}=0$, $h_{j,i}^{*}=0$, otherwise. The $\textit{FDR-
ADDIS-Graph}_{\textit{async}}$ tests each hypothesis $H_{i}$ at significance
level $\alpha_{i}=\min(\hat{\alpha}_{i},\lambda_{i})$, where

$\displaystyle\hat{\alpha}_{i}$
$\displaystyle=(\tau_{i}-\lambda_{i})\left(W_{0}\gamma_{i}+\sum_{j=1}^{i-1}g_{j,i}^{*}(C_{j}-S_{j}+1)\frac{\alpha_{j}}{\tau_{i}-\lambda_{j}}\right.$
$\displaystyle+\left.\sum_{j=1}^{i-1}h_{j,i}^{*}R_{j}[\alpha T_{j}+(\alpha-
W_{0})T_{j}^{c}]\right).$ (11)

The FDR control of $\text{FDR-ADDIS-Graph}_{\text{async}}$ is directly implied
by Theorem 5.2.

##  6 Simulations

We investigate the power and error control of the proposed ADDIS-Graphs by
means of simulations. In Subsection 6.1, we compare the FWER controlling
procedures ADDIS-Graph and ADDIS-Spending (Tian and Ramdas,, 2021) under local
dependence and in Subsection 6.2, we compare the FDR-ADDIS-Graph with the
ADDIS* algorithm (Tian and Ramdas,, 2019) in an asynchronous testing setup.

###  6.1 Simulations for FWER control

We consider $n=1000$ hypotheses to be tested, whose corresponding $p$-values
$(P_{i})_{i\in\\{1,\ldots,n\\}}$ arrive in finite batches
$B_{1},\ldots,B_{n/b}$ with the same batch-size $b\in\\{1,10,25,50\\}$ for
every batch. Let
$X_{bj+1:b(j+1)}=(X_{bj+1},\ldots,X_{b(j+1)})^{T}{\sim}N_{b}(\mu,\Sigma)$,
$j\in\\{0,\ldots,n/b-1\\}$, be $b$-dimensional $i.i.d$ random vectors, where
$\mu=(0,\ldots,0)^{T}\in\mathbb{R}^{b}$ and
$\Sigma=(\sigma_{ij})_{i,j=1,\ldots,b}\in\mathbb{R}^{b\times b}$ with
$\sigma_{ii}=1$ and $\sigma_{ij}=\rho\in(0,1)$ for all $i\in\\{1,\ldots,b\\}$
and $j\neq i$. For each $H_{i}$, $i\in\\{1,\ldots,n\\}$, we test the null
hypothesis $H_{i}:\mu_{i}\leq 0$ with $\mu_{i}=\mathbb{E}[Z_{i}]$, where
$Z_{i}=X_{i}+\mu_{A}$, $\mu_{A}>0$, with probability $\pi_{A}\in(0,1)$ and
$Z_{i}=X_{i}+\mu_{N}$, $\mu_{N}<0$, otherwise. Since the test statistics
follow a standard gaussian distribution under the null hypothesis, a z-test
can be used. The parameter $\mu_{A}$ can be interpreted as the strength of the
alternative, $\pi_{A}$ as probability of a hypothesis being false and
$\mu_{N}$ as the conservativeness of null $p$-values.

In this subsection, we use an overall level $\alpha=0.2$ and estimate the FWER
and power of the $\text{ADDIS-Graph}_{\text{local}}$ and $\text{ADDIS-
Spending}_{\text{local}}$ (Tian and Ramdas,, 2021) by averaging over $2000$
independent trials. Thereby, the proportion of rejected hypotheses among the
false hypotheses is used as empirical power. We set $\mu_{A}=4$,
$\mu_{N}=-0.5$ and $\rho=0.8$ in all simulations within this subsection, thus
obtaining slightly conservative null $p$-values. Since both procedures are
based on the same ADDIS principle and therefore exploit the conservativeness
of null $p$-values in the same manner, no more parameter configurations are
necessary. As recommended by Tian and Ramdas, (2021), we choose the
$\tau_{i}=0.8$ and $\lambda_{i}=\alpha\tau_{i}=0.16$ for all $i\in\mathbb{N}$.
In the first simulation (Figure 4), we also use the same $\gamma_{i}\propto
1/\left((i+1)\log(i+1)^{2}\right)$ as Tian and Ramdas, (2021) in their
simulations. However, in Figures 5 and 6, we use $\gamma_{i}\propto 1/i^{1.6}$
and $\gamma_{i}=6/(\pi^{2}i^{2})$, as the procedures are very sensitive to the
choice of $(\gamma_{i})_{i\in\mathbb{N}}$. For the weights of the ADDIS-Graph,
we always set $g_{j,i}=\gamma_{i-j}$, $j\in\mathbb{N}$ and $i>j$.

Figure 4: Comparison of $\text{ADDIS-Spending}_{\text{local}}$ and
$\text{ADDIS-Graph}_{\text{local}}$ in terms of power and FWER for different
batch-sizes and proportions of false null hypotheses ($\pi_{A}$). Lines above
the overall level $\alpha=0.2$ correspond to power and lines below to FWER.
The $p$-values were generated as described in the text with parameters
$\mu_{N}=-0.5$, $\mu_{A}=4$ and $\rho=0.8$. Both procedures were applied with
parameters $\tau_{i}=0.8$, $\lambda_{i}=0.16$ and $\gamma_{i}\propto
1/\left((i+1)\log(i+1)^{2}\right)$, In addition, $g_{j,i}=\gamma_{i-j}$ was
used in $\text{ADDIS-Graph}_{\text{local}}$. Figure 5: Comparison of
$\text{ADDIS-Spending}_{\text{local}}$ and $\text{ADDIS-Graph}_{\text{local}}$
in terms of power and FWER for different batch-sizes and proportions of false
null hypotheses ($\pi_{A}$). Lines above the overall level $\alpha=0.2$
correspond to power and lines below to FWER. The $p$-values were generated as
described in the text with parameters $\mu_{N}=-0.5$, $\mu_{A}=4$ and
$\rho=0.8$. Both procedures were applied with parameters $\tau_{i}=0.8$,
$\lambda_{i}=0.16$ and $\gamma_{i}\propto 1/i^{1.6}$. In addition,
$g_{j,i}=\gamma_{i-j}$ was used in $\text{ADDIS-Graph}_{\text{local}}$. Figure
6: Comparison of $\text{ADDIS-Spending}_{\text{local}}$ and $\text{ADDIS-
Graph}_{\text{local}}$ in terms of power and FWER for different batch-sizes
and proportions of false null hypotheses ($\pi_{A}$). Lines above the overall
level $\alpha=0.2$ correspond to power and lines below to FWER. The $p$-values
were generated as described in the text with parameters $\mu_{N}=-0.5$,
$\mu_{A}=4$ and $\rho=0.8$. Both procedures were applied with parameters
$\tau_{i}=0.8$, $\lambda_{i}=0.16$ and $\gamma_{i}=6/(\pi^{2}i^{2})$. In
addition, $g_{j,i}=\gamma_{i-j}$ was used in $\text{ADDIS-
Graph}_{\text{local}}$.

The plots indicate that $\text{ADDIS-Spending}_{\text{local}}$ and
$\text{ADDIS-Graph}_{\text{local}}$ perform quite similar under independence
of the $p$-values. However, when the $p$-values become locally dependent the
power of the $\text{ADDIS-Spending}_{\text{local}}$ decreases systematically
in all cases, while the power of the $\text{ADDIS-Graph}_{\text{local}}$
either remains similar (Figure 4) or even increases (Figures 5 and 6). To
understand the power behavior of the $\text{ADDIS-Graph}_{\text{local}}$ note
that the larger the batch-size, the further into the future the significance
level is distributed by the weights $(g^{*}_{j,i})_{i=j+1}^{\infty}$ (see
Definition 4.1). In these simulations $\gamma_{i}\propto
1/\left((i+1)\log(i+1)^{2}\right)$ (Figure 4) decreases the slowest and
$\gamma_{i}=6/(\pi^{2}i^{2})$ (Figure 6) decreases the fastest. If
$(\gamma_{i})_{i\in\mathbb{N}}$ decreases slow and the batch-size is large,
$\text{ADDIS-Graph}_{\text{local}}$ distributes a lot of significance level to
hypotheses in the far future. However, since the testing process is finite in
this case, these hypotheses may never be tested, which leads to a power loss.
On the other hand, if $(\gamma_{i})_{i\in\mathbb{N}}$ decreases fast,
$\text{ADDIS-Graph}_{\text{local}}$ allocates the individual significance
levels more evenly under a larger batch-size, which results in a higher power.
Thus, in order to obtain the optimal power for each batch-size, one could
choose a faster decreasing $(\gamma_{i})_{i\in\mathbb{N}}$ the larger the
batch-size.

###  6.2 Simulations for FDR control

In this subsection we consider the same simulation setup as described in
Subsection 6.1, but for independent $p$-values ($b=1$). However, applying the
procedures, it is assumed that the hypotheses are tested in an asynchronous
manner. Thus, for each hypotheses $H_{i}$, $i\in\mathbb{N}$, we have a
stopping time $E_{i}\geq i$. We assume that $E_{i}=i+e$ for some constant test
duration $e\in\mathbb{N}_{0}$. In the following simulations we compare the
$\text{FDR-ADDIS-Graph}_{\text{async}}$ and $\text{ADDIS}^{*}_{\text{async}}$
(Tian and Ramdas,, 2019) in terms of power and FDR for $e\in\\{0,2,5,10\\}$.
Since FDR is less conservative than FWER, we change the overall level to
$\alpha=0.05$ and strength of the alternative to $\mu_{A}=3$. As recommended
by Tian and Ramdas, (2019), we choose $\tau_{i}=0.5$ and $\lambda_{i}=0.25$
for all $i\in\mathbb{N}$, but use the same $(\gamma_{i})_{i\in\mathbb{N}}$ and
$(g_{j,i})_{j=i+1}^{\infty}$, $j\in\mathbb{N}$, as before. Furthermore, we set
$W_{0}=\alpha$. For the additional weights $(h_{j,i})_{j=i+1}^{\infty}$ of the
$\text{FDR-ADDIS-Graph}_{\text{async}}$, we fix $h_{j,i}=g_{j,i}$ for all
$j\in\mathbb{N}$ and $i>j$. The results obtained by averaging over $200$
independent trials can be found in the Figures 7-9.

Figure 7: Comparison of $\text{ADDIS}^{*}_{\text{async}}$ and $\text{FDR-
ADDIS-Graph}_{\text{async}}$ in terms of power and FDR for different test
durations and proportions of false null hypotheses ($\pi_{A}$). Lines above
the overall level $\alpha=0.05$ correspond to power and lines below to FDR.
The $p$-values were generated as described in the text with parameters
$\mu_{N}=-0.5$ and $\mu_{A}=3$. Both procedures were applied with parameters
$\tau_{i}=0.5$, $\lambda_{i}=0.25$, $\gamma_{i}\propto
1/\left((i+1)\log(i+1)^{2}\right)$ and $W_{0}=\alpha$. In addition,
$g_{j,i}=\gamma_{i-j}$ and $h_{j,i}=g_{j,i}$ were used in $\text{FDR-ADDIS-
Graph}_{\text{async}}$. Figure 8: Comparison of
$\text{ADDIS}^{*}_{\text{async}}$ and $\text{FDR-ADDIS-Graph}_{\text{async}}$
in terms of power and FDR for different test durations and proportions of
false null hypotheses ($\pi_{A}$). Lines above the overall level $\alpha=0.05$
correspond to power and lines below to FDR. The $p$-values were generated as
described in the text with parameters $\mu_{N}=-0.5$ and $\mu_{A}=3$. Both
procedures were applied with parameters $\tau_{i}=0.5$, $\lambda_{i}=0.25$,
$\gamma_{i}\propto 1/i^{1.6}$ and $W_{0}=\alpha$. In addition,
$g_{j,i}=\gamma_{i-j}$ and $h_{j,i}=g_{j,i}$ were used in $\text{FDR-ADDIS-
Graph}_{\text{async}}$. Figure 9: Comparison of
$\text{ADDIS}^{*}_{\text{async}}$ and $\text{FDR-ADDIS-Graph}_{\text{async}}$
in terms of power and FDR for different test durations and proportions of
false null hypotheses ($\pi_{A}$). Lines above the overall level $\alpha=0.05$
correspond to power and lines below to FDR. The $p$-values were generated as
described in the text with parameters $\mu_{N}=-0.5$ and $\mu_{A}=3$. Both
procedures were applied with parameters $\tau_{i}=0.5$, $\lambda_{i}=0.25$,
$\gamma_{i}=6/(\pi^{2}i^{2})$ and $W_{0}=\alpha$. In addition,
$g_{j,i}=\gamma_{i-j}$ and $h_{j,i}=g_{j,i}$ were used in $\text{FDR-ADDIS-
Graph}_{\text{async}}$.

The results are similar as for the FWER controlling procedures (Subsection
6.1). The power of $\text{ADDIS}^{*}_{\text{async}}$ decreases enormously for
an increasing test duration. This decrease can be decelerated by the
$\text{FDR-ADDIS-Graph}_{\text{async}}$ (Figures 7 and 8) or even stopped
(Figure 9), if a faster decreasing $(\gamma_{i})_{i\in\mathbb{N}}$ is chosen.

##  7 Application to International Mouse Phenotyping Consortium data

We illustrate how the proposed $\text{ADDIS-Graph}_{\text{local}}$ could be
used by using the International Mouse Phenotyping (IMPC) data and compare the
results obtained with those obtained using the $\text{ADDIS-
Spending}_{\text{local}}$. The IMPC coordinates a large study which aims to
identify the function of every protein coding gene. To this regard, each of
the 20000 genes is systematically knocked out and the impact on the phenotype
explored. In our evaluation, we use the first 5000 observations of the
database at the Zenodo repository https://zenodo.org/record/2396572, organized
by Robertson et al., (2019). It contains $p$-values that resulted from the
analysis by Karp et al., (2017). These $p$-values follow a natural local
dependence structure: the hypotheses are tested in batches and within each
batch the same mice are used for each hypothesis. Thus, the $p$-values within
a batch depend on each other, but $p$-values from different batches are
independent.

We applied $\text{ADDIS-Spending}_{\text{local}}$ and $\text{ADDIS-
Graph}_{\text{local}}$ with the same parameters as in Subsection 6.1. The
$(\gamma_{i})_{i\in\mathbb{N}}$ was chosen such that $\gamma_{i}\propto
1/\left((i+1)\log(i+1)^{2}\right)$ for all $i\in\mathbb{N}$. The results can
be found in figure 10. The left plot shows the number of rejections achieved
by the two procedures with respect to the FWER level $\alpha$ considered.
Similar to Subsection 6.1, we can see that the ADDIS-Graph allows a
significantly larger number of hypotheses to be rejected than the
$\text{ADDIS-Spending}_{\text{local}}$. The right plot shows the individual
significance levels obtained by the two procedures for the FWER level
$\alpha=0.2$. Note however that for ease of illustration, we omitted the first
100 levels that yielded much higher individual significance levels. It can be
seen that the $\text{ADDIS-Graph}_{\text{local}}$ tests each hypothesis using
higher significance levels than the $\text{ADDIS-Spending}_{\text{local}}$. In
fact, for each FWER level and hypothesis, the individual significance level
obtained by the ADDIS-Graph is greater than or equal to the ADDIS-Spending
level. That means, the ADDIS-Graph rejects all hypotheses that are rejected by
the ADDIS-Spending, but additionally some more.

Figure 10: The left plot shows the number of rejections for different FWER
levels $\alpha$ and the right plot the individual significance levels (for
$\alpha=0.2$) obtained by $\text{ADDIS-Spending}_{\text{local}}$ and
$\text{ADDIS-Graph}_{\text{local}}$. Both procedures were applied with
parameters $\tau_{i}=0.8$, $\lambda_{i}=0.16$ and $\gamma_{i}\propto
1/\left((i+1)\log(i+1)^{2}\right)$. In addition, $g_{j,i}=\gamma_{i-j}$ was
used in $\text{ADDIS-Graph}_{\text{local}}$.

##  8 Conclusion

In this work, we presented a graphical approach to exploit the ADDIS
principles for FWER (Tian and Ramdas,, 2021) and FDR (Tian and Ramdas,, 2019)
control. We started with the construction of an FWER controlling ADDIS-Graph.
This proposal enhances the interpretability of the ADDIS-Spending and also
enlarges the family of procedures that it includes, as we show that by means
of the ADDIS-Graph all procedures that satisfy the ADDIS principle for FWER
control can be obtained. Furthermore, the ADDIS-Graph can easily be adapted to
a local dependence structure and an asynchronous testing setup without losing
significance level. For both situation, in the considered simulation scenarios
we show that the ADDIS-Graph leads to a large power gain as compared to the
ADDIS-Spending. Moreover, we extend the ADDIS-Graph to the FDR control setting
resulting in an FDR-ADDIS-Graph. It has the same advantages as the ADDIS-Graph
and is superior to the currently used ADDIS method with FDR control, the
$\text{ADDIS}^{*}$ algorithm.

Robertson et al., 2022b  claimed that the individual significance levels
assigned by asynchronous online procedures are more conservative. We have
illustrated with the ADDIS-Graph that this is not necessarily the case.
Although the significance level of a hypothesis depends on pessimistic
assumptions about the outcomes of tests that are still running, future
hypotheses can take advantage of this conservatism and achieve higher
significance levels such that no level is lost overall.

We wonder whether the ADDIS-Graph can be extended to further multiple testing
frameworks. For example, Zrnic et al., (2020) considered online batched-
testing, where at each step not only one, but a batch of several hypotheses is
tested at the same time. One could think of an ADDIS-Graph that distributes
significance level to all hypotheses within the considered batch, but outside
the batch only to future hypotheses.

Another task for future work is the optimal choice of the parameters
$(\gamma_{i})_{i\in\mathbb{N}}$, $(g_{j,i})_{j\in\mathbb{N},i>j}$ and
$(h_{j,i})_{j\in\mathbb{N},i>j}$. In our simulations (Section 6), we chose
$(\gamma_{i})_{i\in\mathbb{N}}$ as in the literature for the comparison
procedures and set $(g_{j,i})_{i=j+1}^{\infty}$ and
$(h_{j,i})_{i=j+1}^{\infty}$ related to $(\gamma_{i})_{i\in\mathbb{N}}$ for
each $j\in\mathbb{N}$. However, the large number of parameters allows for many
further possibilities that can strongly influence the performance of the
ADDIS-Graphs. For instance, we saw that a faster decreasing
$(\gamma_{i})_{i\in\mathbb{N}}$ would be useful when the batch-size or test
duration is large. Many more such recommendations could be made through
simulations and theoretical results. In addition, one could study time-varying
choices of $(\tau_{i})_{i\in\mathbb{N}}$ and $(\lambda_{i})_{i\in\mathbb{N}}$
that may depend on the previous test outcomes.

## Appendix

###### Proof of Theorem 3.2.

Let $(\alpha_{i})_{i\in\mathbb{N}}$ be given by the ADDIS-Graph. We need to
show that for any $i\in\mathbb{N}$,
$S_{1:i}\coloneqq(S_{1},\ldots,S_{i})^{T}\in\\{0,1\\}^{i-1}$ and
$C_{1:i}\coloneqq(C_{1},\ldots,C_{i})^{T}\in\\{0,1\\}^{i}$:

$\displaystyle\sum_{j=1}^{i}\frac{\alpha_{i}}{\tau_{i}-\lambda_{i}}(S_{i}-C_{i})\leq\alpha.$
(12)

We define $U_{j}\coloneqq C_{j}-S_{j}+1$ for all $j\in\mathbb{N}$. Then
$1-U_{j}=S_{j}-C_{j}$ and since $C_{j}\leq S_{j}$, it holds
$U_{j}\in\\{0,1\\}$. Now let $i\in\mathbb{N}$ and
$U_{1:i}=(U_{1},\ldots,U_{i})^{T}\in\\{0,1\\}^{i}$ be arbitrary but fixed.
With this, (12) is equivalent to

$\displaystyle F_{i}(U_{1:i})$
$\displaystyle\coloneqq\sum_{j=1}^{i}\left(\alpha\gamma_{j}+\sum_{k=1}^{j-1}g_{k,j}U_{k}\alpha_{k}(U_{1:(k-1)})\frac{1}{\tau_{k}-\lambda_{k}}\right)(1-U_{j})\leq\alpha.$
(13)

Note that we only wrote the dependence of $\alpha_{k}$ on
$U_{1:(k-1)}=(U_{1},\ldots,U_{k-1})^{T}$, although the parameters
$\lambda_{k}$ and $\tau_{k}$ could depend on it as well. That is, because
these parameters could also be fixed, meaning if we change the $U_{1:(k-1)}$
they would still be valid parameters for an ADDIS-Graph. In contrast, the
$\alpha_{k}$ changes by definition. It is difficult to show the validity of
(13) directly. However, we will see that there exists
$\tilde{U}_{1:i}\in\\{0,1\\}^{i}$ that obviously fulfil
$F_{i}(\tilde{U}_{1:i})\leq\alpha$. Therefore, the idea is to determine such a
$\tilde{U}_{1:i}$ that additionally satisfies $F_{i}(U_{1:i})\leq
F_{i}(\tilde{U}_{1:i})$.

Let $l=\max\\{j\in\\{1,\ldots,i\\}:U_{j}=1\\}$ (we set $\max(\emptyset)=0$)
and $U_{1:i}^{l}=(U_{1}^{l},\ldots,U_{i}^{l})^{T}$, where $U_{j}^{l}=U_{j}$
for all $j\neq l$ and $U_{l}^{l}=0$. We assume that $l>0$ (if $l=0$, we later
see $F_{i}(U_{1:i})\leq\alpha$ anyway). In the next step we want to show that
$F_{i}(U_{1:i})\leq F_{i}(U_{1:i}^{l})$. For shorter notation we write
$\alpha_{j}=\alpha_{j}(U_{1:(j-1)})$ and
$\alpha_{j}^{l}=\alpha_{j}(U_{1:(j-1)}^{l})$. Since for all $j\leq i$:
$U_{j}^{l}=U_{j}$ ($j\neq l$), $U_{j}^{l}=0$ ($j\geq l$), $U_{j}=0$ ($j\geq
l+1$) and $\alpha_{j}^{l}=\alpha_{j}$ ($j\leq l$), we have:

$\displaystyle F_{i}(U_{1:i}^{l})-F_{i}(U_{1:i})$
$\displaystyle=\sum_{j=1}^{i}\alpha\gamma_{j}(1-U_{j}^{l})-\sum_{j=1}^{i}\alpha\gamma_{j}(1-U_{j})+\sum_{j=1}^{i}\left(\sum_{k=1}^{j-1}g_{k,j}U_{k}^{l}\alpha_{k}^{l}\frac{1}{\tau_{k}-\lambda_{k}}\right)(1-U_{j}^{l})$
$\displaystyle-\sum_{j=1}^{i}\left(\sum_{k=1}^{j-1}g_{k,j}U_{k}\alpha_{k}\frac{1}{\tau_{k}-\lambda_{k}}\right)(1-U_{j})$
$\displaystyle=\alpha\gamma_{l}+\sum_{j=1}^{i}\left(\sum_{k=1}^{j-1}g_{k,j}U_{k}^{l}\alpha_{k}^{l}\frac{1}{\tau_{k}-\lambda_{k}}\right)(1-U_{j}^{l})-\sum_{j=1}^{i}\left(\sum_{k=1}^{j-1}g_{k,j}U_{k}\alpha_{k}\frac{1}{\tau_{k}-\lambda_{k}}\right)(1-U_{j})$
$\displaystyle=\alpha\gamma_{l}+\sum_{k=1}^{l-1}g_{k,l}U_{k}^{l}\alpha_{k}^{l}\frac{1}{\tau_{k}-\lambda_{k}}+\sum_{j=l+1}^{i}\sum_{k=1}^{l-1}g_{k,j}U_{k}^{l}\alpha_{k}^{l}\frac{1}{\tau_{k}-\lambda_{k}}$
$\displaystyle-\sum_{j=l+1}^{i}\sum_{k=1}^{l}g_{k,j}U_{k}\alpha_{k}\frac{1}{\tau_{k}-\lambda_{k}}$
$\displaystyle=\alpha\gamma_{l}+\sum_{k=1}^{l-1}g_{k,l}U_{k}\alpha_{k}\frac{1}{\tau_{k}-\lambda_{k}}-\sum_{j=l+1}^{i}g_{l,j}\alpha_{l}\frac{1}{\tau_{l}-\lambda_{l}}$
$\displaystyle\geq\alpha\gamma_{l}+\sum_{k=1}^{l-1}g_{k,l}U_{k}\alpha_{k}\frac{1}{\tau_{k}-\lambda_{k}}-\alpha_{l}\frac{1}{\tau_{l}-\lambda_{l}}\stackrel{{\scriptstyle
Def.\ref{def:addis_graph}}}{{=}}0,$

where we used in the inequality that the sequence $(g_{l,j})_{j=l+1}^{\infty}$
is non-negative and sums to at most $1$ for all $l\in\mathbb{N}$.

Since the $U_{1:i}\in\\{0,1\\}^{i}$ was arbitrary, this shows
$F_{i}(U_{1:i})\leq F_{i}(U_{1:i}^{0})$ for all $U_{1:i}\in\\{0,1\\}^{i}$,
where $U_{1:i}^{0}=(0,\ldots,0)^{T}\in\\{0,1\\}^{i}$. Next, we deduce that
$F_{i}(U_{1:i}^{0})\leq\alpha$ and conclude the proof. For this, just
recognize that $U_{1:i}^{0}$ means $U_{j}=0$ for all $j\leq i$. Hence, we
obtain

$\displaystyle F_{i}(U_{1:i}^{0})=\sum_{j=1}^{i}\alpha\gamma_{j}\leq\alpha.$

∎

###### Proof of Theorem 3.3.

Let $G_{1:i}=(R_{1},C_{1},S_{1},\ldots,R_{i},C_{i},S_{i})\in\\{0,1\\}^{3i}$,
then every procedure satisfying the ADDIS principle (Theorem 2.1) is a
sequence of non-negative functions
$(\alpha_{i}(G_{1:(i-1)}))_{i\in\mathbb{N}}$ such that

$\displaystyle\sum_{j\leq
i}\frac{\alpha_{j}(G_{1:(j-1)})}{\tau_{j}-\lambda_{j}}(S_{j}-C_{j})\leq\alpha\quad\text{for
all }i\in\mathbb{N}.$ (14)

Note that the function $\alpha_{i}(G_{1:(i-1)})$ is fully determined through
the information until step $i-1$, hence pessimistic assumptions about $S_{i}$
and $C_{i}$ need to be made in order to satisfy equation (14). Consequently,
the condition of the ADDIS principle is equivalent to

$\displaystyle
0\leq\alpha_{i}(G_{1:(i-1)})\leq(\tau_{i}-\lambda_{i})\left(\alpha-\sum_{j\leq
i-1}\frac{\alpha_{j}(G_{1:(j-1)})}{\tau_{j}-\lambda_{j}}(S_{j}-C_{j})\right)\quad\text{for
all }i\in\mathbb{N}.$ (15)

Let $i\in\mathbb{N}$ and $G_{1:(i-1)}\in\\{0,1\\}^{3(i-1)}$ be arbitrary but
fixed. In addition, let $(\alpha_{j})_{j<i}$ be levels obtained by an ADDIS-
Graph with parameters $(\gamma_{j})_{j<i}$ and $(g_{k,j})_{k<j<i}$. We want to
prove that

$\displaystyle\alpha_{i}(\gamma_{i},(g_{j,i})_{j<i}))=(\tau_{i}-\lambda_{i})\left(\alpha\gamma_{i}+\sum_{j=1}^{i-1}g_{j,i}(C_{j}-S_{j}+1)\frac{\alpha_{j}}{\tau_{i}-\lambda_{j}}\right),$

where $\gamma_{i}\in\left[0,1-\sum_{j=1}^{i-1}\gamma_{j}\right]$ and
$g_{j,i}\in\left[0,1-\sum_{k=j+1}^{i-1}g_{j,k}\right]$,
$j\in\\{1,\ldots,i-1\\}$, can take any value in the interval
$\left[0,(\tau_{i}-\lambda_{i})\left(\alpha-\sum_{j\leq
i-1}\frac{\alpha_{j}}{\tau_{j}-\lambda_{j}}(S_{j}-C_{j})\right)\right]$. Since
$\alpha_{i}$ is continuous in $\gamma_{i}$ and $(g_{j,i})_{j<i}$, it is
sufficient to show that $\alpha_{i}(0,(0)_{j<i})=0$ and
$\alpha_{i}\left(1-\sum_{j=1}^{i-1}\gamma_{j},\left(1-\sum_{k=j+1}^{i-1}g_{j,k}\right)_{j<i}\right)=(\tau_{i}-\lambda_{i})\left(\alpha-\sum_{j\leq
i-1}\frac{\alpha_{j}}{\tau_{j}-\lambda_{j}}(S_{j}-C_{j})\right)$. The first
equation follows immediately, hence we only need to show the second (we set
$U_{j}=C_{j}-S_{j}+1$ for all $j\in\mathbb{N}$):

$\displaystyle\text{
}\alpha_{i}\left(1-\sum_{j=1}^{i-1}\gamma_{j},\left(1-\sum_{k=j+1}^{i-1}g_{j,k}\right)_{j<i}\right)-(\tau_{i}-\lambda_{i})\left(\alpha-\sum_{j=1}^{i-1}\frac{\alpha_{j}}{\tau_{j}-\lambda_{j}}(1-U_{j})\right)$
$\displaystyle=(\tau_{i}-\lambda_{i})\left(\alpha\left(1-\sum_{j=1}^{i-1}\gamma_{j}\right)+\sum_{j=1}^{i-1}\left(1-\sum_{k=j+1}^{i-1}g_{j,k}\right)U_{j}\frac{\alpha_{j}}{\tau_{i}-\lambda_{j}}\right)$
$\displaystyle-(\tau_{i}-\lambda_{i})\left(\alpha-\sum_{j=1}^{i-1}\left(\alpha\gamma_{j}+\sum_{k=1}^{j-1}g_{k,j}U_{k}\frac{\alpha_{k}}{\tau_{k}-\lambda_{k}}\right)(1-U_{j})\right)$
$\displaystyle=(\tau_{i}-\lambda_{i})\left(-\alpha\sum_{j=1}^{i-1}\gamma_{j}U_{j}+\sum_{j=1}^{i-1}U_{j}\frac{\alpha_{j}}{\tau_{i}-\lambda_{j}}-\sum_{j=1}^{i-1}\sum_{k=j+1}^{i-1}g_{j,k}U_{j}\frac{\alpha_{j}}{\tau_{i}-\lambda_{j}}\right.$
$\displaystyle\left.+\sum_{j=1}^{i-1}\sum_{k=1}^{j-1}g_{k,j}U_{k}\frac{\alpha_{k}}{\tau_{k}-\lambda_{k}}-\sum_{j=1}^{i-1}\left(\sum_{k=1}^{j-1}g_{k,j}U_{k}\frac{\alpha_{k}}{\tau_{k}-\lambda_{k}}\right)U_{j}\right)$
$\displaystyle=(\tau_{i}-\lambda_{i})\left(\sum_{j=1}^{i-1}U_{j}\frac{\alpha_{j}}{\tau_{i}-\lambda_{j}}-\sum_{j=1}^{i-1}U_{j}\left(\alpha\gamma_{j}+\sum_{k=1}^{j-1}g_{k,j}U_{k}\frac{\alpha_{k}}{\tau_{k}-\lambda_{k}}\right)\right)=0.$

∎

###### Proof of Theorem 5.2.

Let $\alpha_{j}^{0}=W_{0}\gamma_{j}+\sum_{k=1}^{j-1}h_{k,j}R_{k}[\alpha
T_{k}+(\alpha-W_{0})T_{k}^{c}]$ for all $j\in\mathbb{N}$. Note that

$\displaystyle\sum_{j=1}^{i}\alpha_{j}^{0}$
$\displaystyle=\sum_{j=1}^{i}W_{0}\gamma_{j}+\sum_{j=1}^{i}\sum_{k=1}^{j-1}h_{k,j}R_{k}[\alpha
T_{k}+(\alpha-W_{0})T_{k}^{c}]$ $\displaystyle\leq
W_{0}+\sum_{k=1}^{i-1}R_{k}[\alpha T_{k}+(\alpha-
W_{0})T_{k}^{c}]\sum_{j=k+1}^{i}h_{k,j}$ $\displaystyle\leq
W_{0}+\sum_{k=1}^{i-1}R_{k}[\alpha T_{k}+(\alpha-W_{0})T_{k}^{c}]$
$\displaystyle=W_{0}+(\alpha-W_{0})T_{i}+\alpha(|R(i-1)|-1)T_{i}$
$\displaystyle\leq\alpha(|R(i)|\lor 1)$

With this, the proof can be performed as for Theorem 3.2 by replacing
$\alpha\gamma_{j}$ with $\alpha_{j}^{0}$ on the left side in equation (13) and
$\alpha$ with $\alpha(|R(i)|\lor 1)$ on the right side. ∎

## Funding

L. Fischer acknowledges funding by the Deutsche Forschungsgemeinschaft (DFG,
German Research Foundation) – Project number 281474342/GRK2224/2.

M. Bofill Roig is a member of the EU Patient-centric clinical trial platform
(EU-PEARL). EU-PEARL has received funding from the Innovative Medicines
Initiative 2 Joint Undertaking under grant agreement No 853966. This Joint
Undertaking receives support from the European Union’s Horizon 2020 research
and innovation programme and EFPIA and Children’s Tumor Foundation, Global
Alliance for TB Drug Development non-profit organization, Spring- works
Therapeutics Inc. This publication reflects the author’s views. Neither IMI
nor the European Union, EFPIA, or any Associated Partners are responsible for
any use that may be made of the information contained herein.

## Supplementary Material

The R code for the simulations and case study can be found at the GitHub
repository https://github.com/fischer23/Adaptive-Discard-Graph.

## References

  * 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.
  * Bretz et al., (2009) Bretz, F., Maurer, W., Brannath, W., and Posch, M. (2009).  A graphical approach to sequentially rejective multiple test procedures.  Statistics in medicine, 28(4):586–604.
  * Feng et al., (2022) Feng, J., Pennllo, G., Petrick, N., Sahiner, B., Pirracchio, R., and Gossmann, A. (2022).  Sequential algorithmic modification with test data reuse.  In Uncertainty in Artificial Intelligence, pages 674–684. PMLR.
  * Fischer et al., (2022) Fischer, L., Roig, M. B., and Brannath, W. (2022).  The online closure principle.  arXiv preprint arXiv:2211.11400.
  * 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.
  * Karp et al., (2017) Karp, N. A., Mason, J., Beaudet, A. L., Benjamini, Y., Bower, L., Braun, R. E., Brown, S. D., Chesler, E. J., Dickinson, M. E., Flenniken, A. M., et al. (2017).  Prevalence of sexual dimorphism in mammalian phenotypic traits.  Nature communications, 8(1):1–12.
  * Klinglmueller et al., (2014) Klinglmueller, F., Posch, M., and Koenig, F. (2014).  Adaptive graph-based multiple testing procedures.  Pharmaceutical Statistics, 13(6):345–356.
  * Kohavi et al., (2013) Kohavi, R., Deng, A., Frasca, B., Walker, T., Xu, Y., and Pohlmann, N. (2013).  Online controlled experiments at large scale.  In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1168–1176.
  * Muñoz-Fuentes et al., (2018) Muñoz-Fuentes, V., Cacheiro, P., Meehan, T. F., Aguilar-Pimentel, J. A., Brown, S. D., Flenniken, A. M., Flicek, P., Galli, A., Mashhadi, H. H., Hrabě de Angelis, M., et al. (2018).  The international mouse phenotyping consortium (impc): a functional catalogue of the mammalian genome that informs conservation.  Conservation genetics, 19(4):995–1005.
  * 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.
  * (13) Robertson, D. S., Wason, J., König, F., Posch, M., and Jaki, T. (2022a).  Online error control for platform trials.  arXiv preprint arXiv:2202.03838.
  * (14) Robertson, D. S., Wason, J., and Ramdas, A. (2022b).  Online multiple hypothesis testing for reproducible research.  arXiv preprint arXiv:2208.11418.
  * Robertson et al., (2020) Robertson, D. S., Wason, J. M., and Bretz, F. (2020).  Graphical approaches for the control of generalized error rates.  Statistics in medicine, 39(23):3135–3155.
  * Robertson et al., (2019) Robertson, D. S., Wildenhain, J., Javanmard, A., and Karp, N. A. (2019).  onlinefdr: an r package to control the false discovery rate for growing data repositories.  Bioinformatics, 35(20):4196–4199.
  * Tian and Ramdas, (2019) Tian, J. and Ramdas, A. (2019).  Addis: an adaptive discarding algorithm for online fdr control with conservative nulls.  Advances in neural information processing systems, 32.
  * Tian and Ramdas, (2021) Tian, J. and Ramdas, A. (2021).  Online control of the familywise error rate.  Statistical Methods in Medical Research, 30(4):976–993.
  * Zhao et al., (2019) Zhao, Q., Small, D. S., and Su, W. (2019).  Multiple testing when many p-values are uniformly conservative, with application to testing qualitative interaction in educational interventions.  Journal of the American Statistical Association, 114(527):1291–1304.
  * Zrnic et al., (2020) Zrnic, T., Jiang, D., Ramdas, A., and Jordan, M. (2020).  The power of batching in multiple hypothesis testing.  In International Conference on Artificial Intelligence and Statistics, pages 3806–3815. PMLR.
  * 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.