# Online multiple testing with super-uniformity reward

Sebastian Döhler  Iqraa Meah and Etienne Roquain

###### Abstract

Valid online inference is an important problem in contemporary multiple
testing research, to which various solutions have been proposed recently. It
is well-known that these methods can suffer from a significant loss of power
if the null $p$-values are conservative. This occurs frequently, for instance
whenever discrete tests are performed. To reduce conservatism, we introduce
the method of super-uniformity reward (SURE). This approach works by
incorporating information about the individual null cumulative distribution
functions (or upper bounds of them), which we assume to be available. Our
approach yields several new “rewarded” procedures that theoretically control
online error criteria based either on the family-wise error rate (FWER) or the
marginal false discovery rate (mFDR). We prove that the rewarded procedures
uniformly improve upon the non-rewarded ones, and illustrate their performance
for simulated and real data.

62H15,

62Q05,

false discovery rate,

discrete hypothesis testing,

$p$-values,

super-uniformity,

$\alpha$-investing,

online multiple testing,

###### keywords:

[class=AMS]

###### keywords:

##  1 Introduction

###  1.1 Background

Multiple testing is a well-established statistical paradigm for the analysis
of complex and large-scale data sets, in which each hypothesis typically
corresponds to a scientific question. In the classical situation, the set of
hypotheses should be pre-specified before running the statistical inference.
However, in many contemporary applications, questions arise sequentially, in a
continuous stream, and decisions have to be made one at a time, without
waiting for the end of the stream. This is referred to as the online multiple
testing (OMT) framework, by contrast with the former “offline” setting.
Perhaps the most typical application is the continuous monitoring of A/B tests
in the information technology industry or marketing research (see Kohavi et
al., (2013), Johari et al., (2019) and references therein). This problem also
occurs in medicine Kohavi et al., (2020), soil data sets inference Lark,
(2017), and potentially in any situation where data are accumulated over time
while many intricate scientific questions (and thus new hypotheses) are
expected to emerge during the experiments.

###  1.2 Existing literature on online multiple testing

The literature aiming at control of various error rates in OMT has grown
rapidly in the last few years. As a starting point, the family-wise error rate
(FWER) is the probability of making at least one error in the past
discoveries, and a typical aim is to control it at each time of the stream
(for a formal definition of this and other error rates, see Section 2.2).
Since controlling FWER at a given level $\alpha$ is a strong constraint, it
requires employing a procedure that is conservative thus generally leading to
few discoveries. The typical strategy is to distribute over time the initial
wealth $\alpha$, e.g., testing the $i$-th test at level $\alpha\gamma_{i}$ for
a series $\\{\gamma_{i}\\}_{i\geq 1}$ summing to $1$. This approach is
generally referred to as $\alpha$-spending in the literature (Foster and
Stine,, 2008). A less stringent criterion is the false discovery rate (FDR),
which corresponds to the expected proportion of false discoveries. This
versatile criterion allows much more discoveries than the FWER and has known a
huge success in offline multiple testing literature since its introduction by
Benjamini and Hochberg, (1995), both from a theoretical and practical point of
view. In their seminal work on OMT, Foster and Stine, (2008) extended the FDR
in an online setting by considering the expected proportion of errors among
the past discoveries (actually, considering rather the marginal FDR, denoted
below by mFDR, which is defined as the ratio of the expectations, rather than
the expectation of the ratio). The novel strategy in Foster and Stine, (2008),
which is called $\alpha$-investing, is based on the idea that an mFDR
controlling procedure is allowed to recover some $\alpha$-wealth after each
rejection, which slows down the natural decrease of the individual test
levels. In subsequent papers, many further improvements of this method have
been proposed: first, the $\alpha$-investing rule has been generalized by
Aharoni and Rosset, (2014), while maintaining marginal FDR control. Later,
Javanmard and Montanari, (2018) establish the (non-marginal) FDR control of
these rules, including the LORD (Levels based On Recent Discovery) procedure.
Then, a uniform improvement of LORD, called LORD++, has been proposed by
Ramdas et al., (2017), that maintains FDR/mFDR control while extending the
theory in several directions (weighting, penalties, decaying memory).
Extensions to other specific frameworks have been proposed, including rules
that allow asynchronous online testing Zrnic et al., (2021), maintain privacy
Zhang et al., (2020), and accommodate a high-dimensional regression model
Johnson et al., (2020). Next, other works have investigated the case of
sequential testing driven by a special structure, as directed acyclic graphs
Ramdas et al., 2018a , or ordered hypothesis testing with a cutoff decision
time Li and Barber, (2017). Other online error criteria have also been
explored, with false discovery exceedance Javanmard and Montanari, (2018); Xu
and Ramdas, (2021), post hoc false discrovery proportion bounds Katsevich and
Ramdas, (2020), or confidence intervals with false coverage rate control
Weinstein and Ramdas, (2020). Since the online framework is more constrained
than the offline framework, the employed procedures are necessarily less
powerful in that context. Hence, another important branch of the literature
aims at proposing improved rules that gain more discoveries: first, following
the classical “adaptive” offline strategy, procedures can be made less
conservative by implicitly estimating the amount of true null hypotheses, see
the SAFFRON procedure for FDR and the ADDIS-spending procedure for FWER.
Second, under an assumption on the null distribution, increasing the number of
discoveries is possible by “discarding” tests with a too large $p$-value
(Ramdas et al., 2018b, ; Tian and Ramdas,, 2021, 2019). A power enhancement
can also be obtained by combining online procedures with other methods. A
natural idea is to use more sophisticated individual tests in the first place,
e.g., based on multi-armed bandits Yang et al., (2017), or so-called “always
valid $p$-values”, see Johari et al., (2019) and references therein. Another
idea is to combine offline procedures to form “mini-batch” rules, see Zrnic et
al., (2020). Further improvements are also possible by incorporating
contextual information as done by Chen and Kasiviswanathan, (2020) or a using
local FDR like approach, see Gang et al., (2020). Lastly, performance
boundaries have been derived by Chen and Arias-Castro, (2021).

However, in previous literature, a (potentially severe) source of
conservativeness has been ignored so far. Namely, in many applications,
individual tests are based on counts or contingency tables, for instance:

  * •

in web design and marketing, internet companies continually test one web
presentation against another by comparing countable variables like click
numbers, or buying decisions;

  * •

in clinical studies, the efficiency or safety of drugs are compared by
counting patients who survive a certain period after being treated, or who
experience a certain type of adverse drug reaction;

  * •

in biology, the genotype effect on the phenotype can be tested by knocking out
genes sequentially in time.

As a case in point, the data from the International Mouse Phenotyping
Consortium (IMPC, see Muñoz-Fuentes et al., (2018)) frequently used in OMT
(see e.g., Tian and Ramdas,, 2021; Xu and Ramdas,, 2021; Karp et al.,, 2017)
contains many categorical variables. Data analysis of such counts and
contingency tables often involve conservative statistical tests, see Section 6
for more details. While this is a well-known – somewhat unsolvable – problem
in the single testing case, the multiplicity can, perhaps surprisingly, help
to eliminate a part of this conservativeness, even without using a randomized
decision. An active research area explores this phenomenon in the offline
setting, with the seminal works of (Tarone,, 1990; Westfall and Wolfinger,,
1997; Gilbert, 2005a, ) and the subsequent studies of Heyse, (2011); Heller
and Gur, (2011); Dickhaus et al., (2012); Habiger, (2015); Chen et al.,
(2015); Döhler, (2016); Chen et al., (2018); Döhler et al., (2018); Durand et
al., (2019), see also references therein. The present work shows that such an
improvement is also possible in the online setting, as far as FWER or mFDR
control is concerned.

Error rate | Procedure | Critical values | Results
---|---|---|---
FWER | OB | $\alpha^{\mbox{\tiny OB}}_{T}=\alpha\gamma_{T}$ | Tian and Ramdas, (2021)
| AOB | $\begin{aligned} \alpha^{\mbox{\tiny AOB}}_{T}=\alpha(1-\lambda)\gamma_{\mathcal{T}(T)}\end{aligned}$ | Tian and Ramdas, (2021)
mFDR | LORD | $\begin{aligned} \alpha^{\mbox{\tiny LORD}}_{T}=&W_{0}\gamma_{T}+(\alpha-W_{0})\gamma_{T-\tau_{1}}\\\ &+\alpha\sum_{j\geq 2}\gamma_{T-\tau_{j}}\end{aligned}$ | $\begin{aligned} &\mbox{\cite[cite]{\@@bibref{Authors Phrase1YearPhrase2}{JM2018}{\@@citephrase{(}}{\@@citephrase{)}}}}\\\ &\mbox{and \cite[cite]{\@@bibref{Authors Phrase1YearPhrase2}{ ramdas2017online}{\@@citephrase{(}}{\@@citephrase{)}}}}\end{aligned}$
| ALORD | $\begin{aligned} \alpha^{\mbox{\tiny ALORD}}_{T}=(1-\lambda)\cdot&\Big{(}W_{0}\gamma_{\mathcal{T}_{0}(T)}+(\alpha-W_{0})\gamma_{\mathcal{T}_{1}(T)}\\\ &+\alpha\sum_{j\geq 2}\gamma_{\mathcal{T}_{j}(T)}\Big{)}\end{aligned}$ | $\begin{subarray}{c}\mbox{\cite[cite]{\@@bibref{Authors Phrase1YearPhrase2}{ramdas2019saffron}{\@@citephrase{(}}{\@@citephrase{)}}}}\\\ \mbox{(slightly improved)}\end{subarray}$
Table 1: Overview of the critical values of the base procedures for some choice of level $\alpha\in(0,1)$, adaptivity parameter $\lambda\in[0,1)$, initial wealth $W_{0}\in(0,\alpha)$, and spending sequence $(\gamma_{j})_{j\geq 1}$. The quantities $\mathcal{T}(\cdot)$, $\tau_{j}$, $\mathcal{T}_{j}(\cdot)$ are given by (16), (22), (28), respectively. Error rate | Procedure | Critical values | Results
---|---|---|---
FWER |  $\rho$OB | $\begin{aligned} \alpha^{\mbox{\tiny$\rho$OB}}_{T}&=\alpha^{\mbox{\tiny OB}}_{T}+\sum_{t=1}^{T-1}\gamma^{\prime}_{T-t}\rho_{t}\end{aligned}$ | Theorem 3.1
|  $\rho$AOB | $\begin{aligned} \alpha^{\mbox{\tiny$\rho$AOB}}_{T}&=\alpha^{\mbox{\tiny AOB}}_{T}+\sum_{1\leq t\leq T-1\atop p_{t}>\lambda}\gamma^{\prime}_{T-t}\rho_{t}+\varepsilon_{T-1}\end{aligned}$ | Theorem 3.2
mFDR |  $\rho$LORD | $\begin{aligned} \alpha^{\mbox{\tiny$\rho$LORD}}_{T}=&\alpha^{\mbox{\tiny LORD}}_{T}+\sum_{t=1}^{T-1}\gamma^{\prime}_{T-t}\rho_{t}\end{aligned}$ | Theorem 4.1
|  $\rho$ALORD | $\begin{aligned} \alpha^{\mbox{\tiny$\rho$ALORD}}_{T}&=\alpha^{\mbox{\tiny ALORD}}_{T}+\sum_{1\leq t\leq T-1\atop p_{t}>\lambda}\gamma^{\prime}_{T-t}\rho_{t}+\varepsilon_{T-1}\end{aligned}$ | Theorem 4.2
Table 2: Overview of the critical values of the rewarded procedures denoted as
the corresponding base procedures, with an additional symbol “$\rho$” in the
name. Here, $\alpha^{\mbox{\tiny OB}}_{T},\alpha^{\mbox{\tiny
AOB}}_{T},\alpha^{\mbox{\tiny LORD}}_{T},\alpha^{\mbox{\tiny ALORD}}_{T}$ are
the base procedures from Table 1 (with the adaptivity parameter $\lambda$
defined there), $\rho_{t}$ is the super-uniformity reward at time $t$ given by
(8), $\gamma^{\prime}$ is the SURE spending sequence defined in Section 2.4
and
$\varepsilon_{T}={\mathbf{1}\\{p_{T}<\lambda\\}}(\alpha_{T}-\alpha^{0}_{T})$
is an additional adaptivity reward, for either
$(\alpha^{0}_{T},\alpha_{T})=(\alpha^{\mbox{\tiny
AOB}}_{T},\alpha^{\mbox{\tiny$\rho$AOB}}_{T})$, or
$(\alpha^{0}_{T},\alpha_{T})=(\alpha^{\mbox{\tiny
ALORD}}_{T},\alpha^{\mbox{\tiny$\rho$ALORD}}_{T})$, depending on the case.

###  1.3 Contributions of the paper

In this paper, we propose uniform improvements of several classical base
procedures listed in Table 1, and prove control of the corresponding error
rates. A distinguishing feature of our work is that we assume that a (non-
trivial) upper bound for the null cumulative distribution function’s (c.d.f.)
called the null bounding family (see Section 2.1) is known. By combining this
information with base procedures, we construct more efficient OMT procedures
(see Table 2). The key quantity involved in this construction can be
interpreted as a reward (more details will be provided in Section 2.3) induced
by the super-uniformity of the null bounding family. Therefore, we use the
acronym SURE (Super-Uniform-REward) to refer to these new procedures. When we
use the uniform null bounding family (i.e. the classical framework), our SURE
procedures reduce to their base counterparts. Our main contributions are as
follows:

  * •

We propose two new SURE procedures for online FWER control in Section 3: the
first one ($\rho$OB) uniformly improves upon the Online Bonferroni procedure
(OB), while the second ($\rho$AOB) uniformly improves upon the adaptive
spending procedure of Tian and Ramdas, (2021) (AOB).

  * •

We propose two new SURE procedures for online mFDR control in Section 4: the
first one ($\rho$LORD) uniformly improves upon the LORD++ procedures of
(Javanmard and Montanari,, 2018; Ramdas et al.,, 2017) (LORD), while the
second one ($\rho$ALORD) uniformly improves upon the SAFFRON procedure of
Ramdas et al., 2018b  (ALORD).

  * •

We present a general and simple way of constructing SURE procedures for any
base procedure satisfying some mild conditions, see Section 3.4 for FWER and
Section 4.4 for mFDR. This allows us to obtain concise proofs for all our
results, which are deferred to Appendix A.

  * •

We evaluate the performances of the new SURE procedures with simulated
experiments (Section 5) and for a classical real data set (Section 6), where
each hypothesis is tested using a (discrete) Fisher exact test. The gain in
power is shown to be substantial when the discreteness is high, that is, when
the counts in the contingency table are moderate. This improvement is also
shown to be significant on the real data application.

For easier readability of the paper, a succinct overview of our work is
presented in Tables 1 and 2. It lists the base and SURE procedures and
provides links to definitions and results for error rate control.

###  1.4 Relation to adaptive discarding

As Tian and Ramdas, (2019) pointed out, online multiple testing procedures
frequently suffer from significant power loss if the null $p$-values are too
conservative. In Tian and Ramdas, (2021) (FWER control) and Tian and Ramdas,
(2019) (mFDR control), the authors propose adaptive discarding (ADDIS)
approaches as improved methods. In particular, an idea is to use a discarding
rule, that avoids testing a null when the corresponding $p$-value exceeds a
given threshold. The resulting online error rate control holds if the c.d.f.
of the null distribution is convex. In our work, we focus on another type of
super-uniformity induced by discrete tests. Since the c.d.f.’s of the null
distributions are not convex in this case, we cannot use ADDIS while ensuring
type I error rate control. Nevertheless, we include these ADDIS procedures in
our numerical experiments for comparison, see Section 5.

##  2 Preliminaries

###  2.1 Setting, procedure and assumptions

Let $X=(X_{t},t\in\\{1,2,\dots\\})$ be a process composed of random variables.
We denote the distribution of $X$ by $P$, which is assumed to belong to some
distribution set $\mathcal{P}$. We consider an online testing problem where,
at each time $t\geq 1$, the user only observes variable $X_{t}$ and should
test a new null hypothesis $H_{t}$, which corresponds to some subset of
$\mathcal{P}$, typically defined from the distribution of $X_{t}$. We let
$\mathcal{H}_{0}=\mathcal{H}_{0}(P)=\\{t\geq 1\>:\>\mbox{$H_{t}$ is satisfied
by $P$}\\}$ the set of (unknown) times where the corresponding null hypothesis
is true. Throughout the manuscript, we focus on decisions based upon
$p$-values. Hence, we suppose that at each time $t$, we have at hand a
$p$-value $p_{t}=p_{t}(X_{t})\in[0,1]$ (only depending on $X_{t}$) for testing
$H_{t}$, and we consider online multiple testing procedures based on $p$-value
thresholding. This means that each null $H_{t}$ is rejected whenever
$p_{t}(X_{t})\leq\alpha_{t}$, where
$\alpha_{t}=\alpha_{t}(X_{1:(t-1)})\in[0,\infty)$ is a nonnegative threshold,
called a critical value, that is allowed to depend on the data
$X_{1:(t-1)}:=(X_{1},\dots,X_{t-1})$. In other words, $\alpha_{t}$ is
measurable with respect to the $\sigma$-field
$\mathcal{F}_{t-1}=\sigma(X_{1:(t-1)})$. In the literature, this property is
referred to as predictability, see Ramdas et al., (2017). Throughout the
manuscript, an online multiple testing procedure is identified with a family
$\mathcal{A}=\\{\alpha_{t},t\geq 1\\}$ of such predictable critical values.
Let us now state the assumptions used in what follows. First, recall the
classical super-uniformity assumption:

$\mathbf{P}_{X\sim P}(p_{t}(X_{t})\leq u)\leq u\>\text{ for all
}u\in[0,1],\mbox{ and }P\in\mathcal{P}\mbox{ with }t\in\mathcal{H}_{0},$ (1)

which means that each test rejecting $H_{0,t}$ when $p_{t}(X_{t})$ is smaller
than or equal to $u$ is of level $u$. Here, we typically consider a setting
where these tests may have a more stringent level. Formally, at each time $t$,
there is a known null function $F_{t}:[0,1]\to[0,1]$ satisfying

$\displaystyle\mathbf{P}_{X\sim P}\left(p_{t}(X_{t})\leq u\right)\leq
F_{t}(u)\leq u,\>\text{for all }u\in[0,1],\mbox{ and }P\in\mathcal{P}\mbox{
with }t\in\mathcal{H}_{0}.$ (2)

Note that we will sometimes also consider $F_{t}(u)$ for $u\geq 1$, in which
it is to be understood as $F_{t}(u\wedge 1)$. This makes equation
$F_{t}(u)\leq u$ still valid under (2). The function family
$\mathcal{F}=\\{F_{t},t\geq 1\\}$ will be referred to as the null bounding
family. Note that (2) reduces to (1) when choosing $F_{t}(u)=u$ for all $u$,
but encompasses other cases by choosing differently the null bounding family.
Typically, for discrete tests, it is well-known that $F_{t}(u)$ can be (much)
smaller than $u$, see Example 2.1 for more details. Second, another important
assumption is the online independence within the $p$-value process:

$p_{t}(X_{t})$ is independent of the past $X_{1:(t-1)}$ for all
$t\in\mathcal{H}_{0}$ and $P\in\mathcal{P}$. (3)

Assumption (3) holds in the case where the variables in $(X_{t},t\geq 1)$ are
all mutually independent, which means that the data are collected
independently at each time.

######  Remark 2.1.

In this manuscript, results are often based on assumptions (2) and (3). In all
these results, these two assumptions can be replaced by the weaker condition

$\mathbf{P}_{X\sim P}(p_{t}(X_{t})\leq u\>|\>X_{1:(t-1)})\leq F_{t}(u)\leq
u\>\text{ a.s. for all }u\in[0,1],\mbox{ for all }t\in\mathcal{H}_{0}\mbox{
and }P\in\mathcal{P}.$ (4)

When choosing the null bounding family $F_{t}(u)=u$ for all $u$, the latter
condition is sometimes referred to as SuperCoAD (super-uniformity
conditionally on all discoveries), see Ramdas et al., (2017).

######  Remark 2.2.

Formally, (3) is slightly different from the usual offline independence
assumption saying that the $p$-values in $(p_{t},t\in\mathcal{H}_{0})$ are
mutually independent, and independent of the false null $p$-value family
$(p_{t}(X_{t}),t\notin\mathcal{H}_{0})$. For instance, in (3), the variable
$p_{1}$ is not assumed to be independent of the future false null $p$-values
$(p_{t},t\notin\mathcal{H}_{0},t\geq 2)$.

######  Example 2.1.

Our leading example is the case where a discrete test statistic is used for
inference in each individual test. Typical instances include tests for
analyzing counts represented by contingency tables, such as Fisher’s exact
test, see Section 5. In discrete testing, each $p$-value $p_{t}(X_{t})$ has
its own support $\mathcal{S}_{t}$ (known and not depending on $P$), that is a
finite set (or, in full generality, a countable set with $0$ as the only
possible accumulation point). A null bounding family satisfying (2) can easily
be derived by considering $F_{t}$, the right-continuous step function that
jumps at each point of $\mathcal{S}_{t}$, see Figure 2. Note that the supports
$\mathcal{S}_{t}$ depends on $t$ so that discrete testing also induces
heterogeneity across time.

###  2.2 Error rates and power

Let us define the criteria that we use to measure the quality of a given
procedure $\mathcal{A}=\\{\alpha_{t},t\geq 1\\}$. For each $T\geq 1$, let
$\mathcal{R}(T)=\\{t\in\\{1,\dots,T\\}\>:\>p_{t}(X_{t})\leq\alpha_{t}\\}$
denote the set of rejection times of the procedure $\mathcal{A}$, up to time
$T$. We consider the two following classical online criteria for type I error
rates:

$\displaystyle\textnormal{FWER}(\mathcal{A},P)$ $\displaystyle:=\sup_{T\geq
1}\\{\textnormal{FWER}(T,\mathcal{A},P)\\},\qquad\text{{where}}$
$\displaystyle\textnormal{FWER}(T,\mathcal{A},P)$
$\displaystyle:=\mathbf{P}_{X\sim
P}\Big{(}|\mathcal{H}_{0}\cap\mathcal{R}(T)|\geq 1\Big{)};$
$\displaystyle\textnormal{mFDR}(\mathcal{A},P)$ $\displaystyle:=\sup_{T\geq
1}\\{\textnormal{mFDR}(T,\mathcal{A},P)\\},\qquad\text{{where}}$
$\displaystyle\textnormal{mFDR}(T,\mathcal{A},P)$
$\displaystyle:=\frac{\mathbf{E}_{X\sim
P}\left(|\mathcal{H}_{0}\cap\mathcal{R}(T)|\right)}{\mathbf{E}_{X\sim
P}\left(1\vee|\mathcal{R}(T)|\right)},$ (6)

with the convention $0/0=0$. In words, when controlling the online FWER at
level $\alpha$, one has the guarantee that, at each fixed time $T$, the
probability of making at least one false discovery before time $T$ is below
$\alpha$. Since FWER control does not tolerate any false discovery (with high
probability), it is generally considered a stringent criterion. By contrast,
when controlling the online mFDR, at each time $T$, the expected number of
false discoveries before time $T$ can be non-zero, but in an amount controlled
by the expected number of discoveries before time $T$. While online FWER has
been investigated in Tian and Ramdas, (2021), online mFDR control is generally
less conservative (that is, allows more discoveries), and is widely used in an
online context, see Foster and Stine, (2008); Ramdas et al., (2017); Ramdas et
al., 2018b . The false discovery rate (FDR) is close to the mFDR: it is
defined by using the expectation of the ratio, instead of the ratio of the
expectations as in (6). Controlling the FDR generally requires more
assumptions, while mFDR is particularly useful in an online context (we refer
the reader to Section 1.1 of Zrnic et al., (2021) for more discussions on
this). For a given error rate, we aim at deriving procedures that maximize
power. For any procedure $\mathcal{A}$, we define the power as the expected
proportion of signal the procedure can detect, that is,

$\displaystyle\text{Power}(T,\mathcal{A},P):=\frac{\mathbf{E}_{X\sim
P}\left(|\mathcal{H}_{1}\cap\mathcal{R}(T)|\right)}{1\vee\lvert\mathcal{H}_{1}\lvert},$
(7)

where $\mathcal{H}_{1}$ is the set of times of false nulls, that is, the
complement of $\mathcal{H}_{0}$ in $\\{1,2,\dots\\}$. While this power notion
will be used in our numerical experiments to compare procedures, our
theoretical results will use a stricter comparison criterion. For two
procedures $\mathcal{A}=\\{\alpha_{t},t\geq 1\\}$ and
$\mathcal{A}^{\prime}=\\{\alpha^{\prime}_{t},t\geq 1\\}$, we say that
$\mathcal{A}^{\prime}$ uniformly dominates $\mathcal{A}$ when
$\alpha^{\prime}_{t}\geq\alpha_{t}$ for all $t\geq 1$ (almost surely). This
implies that, almost surely, $\mathcal{A}^{\prime}$ makes more discoveries
than $\mathcal{A}$, in the sense that the set of discoveries of $\mathcal{A}$
is contained in the one of $\mathcal{A}^{\prime}$, that is,
$\mathcal{R}(T)\subset\mathcal{R}^{\prime}(T)$ for all $T\geq 1$ (a.s.). In
particular, this implies the same domination for the true discovery sets and
thus in particular
$\text{Power}(T,\mathcal{A},P)\leq\text{Power}(T,\mathcal{A}^{\prime},P)$ for
all $T\geq 1$. With this terminology, we can restate the aim of this work as
follows: construct valid OMT procedures that uniformly dominate their base
procedures by incorporating the null bounding family $F_{t}$ given in (2).

###  2.3 Wealth and super-uniformity reward

In the Generalized Alpha-Investing paradigm (see Xu and Ramdas, (2021) and the
references given therein), the nominal level $\alpha$, at which one wants to
control the type I error rate, can be seen as an overall error budget – or
wealth – that may be spent on testing hypotheses in the course of an online
experiment. For a given OMT procedure $\mathcal{A}$, it is possible to define
a suitable wealth function $W(T)=W(T,\mathcal{A},P)$, such that $W(T)$
represents the wealth available at time $T$ for further testing. As a case in
point, Xu and Ramdas, (2021) define the (nominal) wealth function for the
online Bonferroni procedure by
$W^{\textnormal{nom}}(T)=\alpha-\sum_{t=1}^{T}\alpha\gamma_{t}$. Generalizing
this expression for arbitrary null distributions we obtain the “true” or
“effective” wealth
$W^{\textnormal{eff}}(T)=\alpha-\sum_{t=1}^{T}F_{t}(\alpha\gamma_{t})$, where
$F_{t}$ is a null-bounding function. In the super-uniform setting, assumption
(2) implies $W^{\textnormal{nom}}(T)\leq W^{\textnormal{eff}}(T)$, and as the
two orange curves in Figure 1 illustrate, the discrepancy can be quite large.

Figure 1: Nominal wealth for OB (dashed orange curve), effective wealth for OB
(solid orange curve) and effective wealth for $\rho$OB (solid green curve) for
the male mice from the IMPC data (see Section 6 for more details).

However, while the user thinks the procedure is spending the budget across
time according to the nominal wealth given by the dashed orange curve, in
reality, the procedure is under-utilizing wealth, as the solid orange true
wealth curve indicates. This unnecessarily austere spending behavior makes the
online Bonferroni procedure sub-optimal. In addition, this phenomenon extends
to the other procedures and error rates listed in Table 1 as well. Our
proposed solution incorporates super-uniformity so that its wealth function
behaves like the targeted nominal wealth, as depicted by the green curve in
Figure 1.

For incorporating super-uniformity, we introduce the super-uniformity reward
(SURE), a key quantity in our work. For any procedure
$\mathcal{A}=\\{\alpha_{t},t\geq 1\\}$ and null bounding family
$\mathcal{F}=\\{F_{t},t\geq 1\\}$, the super-uniformity reward $\rho_{t}$ at
time $t$ is defined by

$\displaystyle\rho_{t}=\rho_{t}(\alpha_{t},F_{t}):=\alpha_{t}-F_{t}(\alpha_{t}),\quad
t\geq 1.$ (8)

Note that (2) always implies $\rho_{t}\geq 0$ for all $t\geq 1$. In the case
of discrete testing (Example 2.1), we have $F_{t}(\alpha_{t})=0$ when
$\alpha_{t}$ is below the infimum of the support $\mathcal{S}_{t}$. This
produces the maximum possible super-uniformity reward at time $t$, that is,
$\rho_{t}=\alpha_{t}$. Conversely, when $\alpha_{t}\in\mathcal{S}_{t}$, we
have $F_{t}(\alpha_{t})=\alpha_{t}$ and we have no super-uniformity reward at
time $t$, that is, $\rho_{t}=0$. In general, we have
$\rho_{t}\in[0,\alpha_{t}]$, its actual value depending on the discreteness of
the test (that is on the steps of $F_{t}$) and of the value of $\alpha_{t}$.
The super-uniformity reward is illustrated in Figure 2 for a single
distribution $F_{t}$ and value $\alpha_{t}$.

Figure 2: Super-uniformity reward $\rho_{t}$ at time $t$ (length of the
vertical line) as defined by (8) for a given function $F_{t}$ (orange step
function) and a critical value $\alpha_{t}$ (triangle). The dashed line is the
identity function $x\in[0,1]\mapsto x$.

Mathematically, $\rho_{t}$ is simply the difference between the nominal
significance level $\alpha_{t}$, and the truly achieved significance level
$F_{t}(\alpha_{t})$. In terms of wealth, $\rho_{t}$ can be interpreted as the
fraction of nominal significance level which the OMT procedure was unable to
“spend” due to super-uniformity. Intuitively, it seems clear that this amount
can be put aside and be re-allocated to the subsequent tests to increase the
future critical values $(\alpha_{T},T\geq t+1)$. In Sections 3 and 4, we show
in detail how this can be done without sacrificing type I error control.

###  2.4 Spending sequences

As Table 1 displays, the base procedures we use are parametrized by a sequence
$\gamma=(\gamma_{t})_{t\geq 1}$ of non-negative values, such that $\sum_{t\geq
1}\gamma_{t}\leq 1$, which we refer to as the spending sequence. The spending
sequence controls the rate at which the wealth is spent in the course of the
online experiment (for instance, see (10) for the online Bonferroni
procedure). However, finding suitable spending sequences is not trivial: there
is a trade-off between saving wealth for large values of $T$ and the ability
to make discoveries in the not-too-distant future. Typical choices for
$\gamma$ in the literature are:

  * •

$\gamma_{t}\propto t^{-q}$ for all $t$ for some $q>1$, (see Tian and Ramdas,,
2021);

  * •

$\gamma_{t}\propto(t+1)^{-1}\log^{-q}(t+1)$ for all $t$, for some $q>1$, (see
Tian and Ramdas,, 2021);

  * •

$\gamma_{t}\propto\frac{\log((t+1)\vee 2)}{(t+1)\exp(\sqrt{\log(t+1)})}$ (see
Javanmard and Montanari, (2018)).

Throughout the paper, we choose $\gamma_{t}\propto t^{-q}$ with $q=1.6$, as
suggested by previous literature. In the base procedures listed in Table 1,
there are two potential sources of wealth: the initial wealth invested at
$T=0$, and the rejection reward that can be earned by rejections for investing
procedures (i.e., mFDR controlling procedures). When one can use super-
uniformity reward as described in Section 2.3, an additional source of wealth
comes into play. Indeed, our approach is to use an additional SURE spending
sequence $\gamma^{\prime}$ to smoothly incorporate all the rewards collected
up to time $T$ to compute the new critical value $\alpha_{T}$. This SURE
spending sequence could be chosen for instance from one of the smoothing
sequences listed above. Here, we focus on the following choice:

$\gamma^{\prime}_{t}=\gamma^{\prime}_{t}(h)={\mathbf{1}\\{t\leq
h\\}}/h,\>\>\>\>t\geq 1,$ (9)

where $h\geq 1$ is a suitably chosen integer. Since this leads to procedures
that spread rewards uniformly over a finite horizon of length $h$, we refer to
(9) – by analogy with non-parametric density estimation – as a rectangular
kernel with bandwidth $h$. Finally, another idea introduced by Ramdas et al.,
2018b ; Tian and Ramdas, (2021) in order to slow down the natural decay in the
$\alpha_{t}$ sequence is to consider $\gamma_{\mathcal{T}(t)}$ where
$\mathcal{T}(t)$ is a slowed down clock, see (16) and (28) below. As we will
see in Section 3.3 and Section 4.3, this technique can also be combined with
suitable super-uniformity rewarding.

##  3 Online FWER control

In this section, we aim at finding procedures $\mathcal{A}$ such that
$\textnormal{FWER}(\mathcal{A},P)\leq\alpha$ for some targeted level
$\alpha\in(0,1)$. We begin with a simple application of our approach to
improve the online Bonferroni procedure with a “greedy” super-uniformity
reward, and then turn to a smoother spending of the super-uniformity reward
(Theorem 3.1). This approach is then applied in combination with the adaptive
online procedure introduced by Tian and Ramdas, (2021) (Theorem 3.2). Finally,
a general result is provided (Theorem 3.3) that allows rewarding any procedure
controlling the online FWER in some specific way. This allows unifying all
results obtained in this section while further extending the scope of our
methodology.

###  3.1 Warming-up: online Bonferroni procedure and a first greedy reward

For any given spending sequence sequence $\gamma=(\gamma_{t})_{t\geq 1}$, a
well-known online FWER controlling procedure is the online Bonferroni
procedure, $\mathcal{A}^{\mbox{\tiny OB}}=\mathcal{A}^{\mbox{\tiny
OB}}(\alpha,\gamma):=\\{\alpha^{\mbox{\tiny OB}}_{t},t\geq 1\\}$, defined by

$\displaystyle\alpha^{\mbox{\tiny OB}}_{T}:=\alpha\gamma_{T},\quad T\geq 1.$
(10)

It is also called Alpha-Spending rule (Foster and Stine,, 2008) in the context
of online FWER control, see Tian and Ramdas, (2021). It is straightforward to
check that $\mathcal{A}^{\mbox{\tiny OB}}$ controls the FWER under the
classical super-uniformity condition (1): by the Markov inequality, for all
$T\geq 1$,

$\displaystyle\textnormal{FWER}(T,\mathcal{A}^{\mbox{\tiny OB}},P)$
$\displaystyle\leq\mathbf{E}_{X\sim
P}\Big{(}\sum_{t=1}^{T}{\mathbf{1}\\{t\in\mathcal{H}_{0},p_{t}\leq\alpha\gamma_{t}\\}}\Big{)}$
(11) $\displaystyle\leq\sum_{t\in\mathcal{H}_{0}}\mathbf{P}_{X\sim
P}(p_{t}\leq\alpha\gamma_{t})\leq\sum_{t\in\mathcal{H}_{0}}\alpha\gamma_{t}\leq\alpha.$
(12)

Let us now present the rationale behind of our approach in this simple case.
Assume more generally that we have at hand a null bounding family
$\mathcal{F}=\\{F_{t},t\geq 1\\}$ satisfying (2). The above reasoning leads to
the following valid bound for any procedure $\mathcal{A}=\\{\alpha_{t},t\geq
1\\}$ (with deterministic $\alpha_{t}$):

$\displaystyle\textnormal{FWER}(T,\mathcal{A},P)$
$\displaystyle\leq\sum_{t=1}^{T}F_{t}(\alpha_{t})\leq\alpha_{T}+\sum_{t=1}^{T-1}F_{t}(\alpha_{t})=\alpha\sum_{t=1}^{T}\gamma_{t}\leq\alpha,$
(13)

by choosing
$\alpha_{T}=\sum_{t=1}^{T}\alpha\gamma_{t}-\sum_{t=1}^{T-1}F_{t}(\alpha_{t})$.
The latter is a recursive relation that allows to define a new procedure
$\mathcal{A}=\\{\alpha_{t},t\geq 1\\}$ controlling the FWER. Since
$\alpha_{1}=\alpha\gamma_{1}$ and for $T\geq 2$,
$\alpha_{T}-\alpha_{T-1}=\alpha\gamma_{T}-F_{T-1}(\alpha_{T-1})$, this leads
to the simple rule

$\displaystyle\alpha_{T}=\alpha\gamma_{T}+\rho_{T-1},\quad T\geq 1,$ (14)

where $\rho_{T-1}=\alpha_{T-1}-F_{T-1}(\alpha_{T-1})$ is the super-uniformity
reward (8) at time $T-1$ (with the convention $\rho_{0}=0$). In addition, from
(2), we have $\rho_{T-1}\geq 0$, and the critical values (14) uniformly
dominate the online Bonferroni critical values (10) (the obtained critical
values are in particular nonnegative, thus defining a valid OMT procedure).
The approach behind critical values (14) is said here to be “greedy”, because
it spends the complete super-uniformity reward $\rho_{T-1}$ obtained at step
$T-1$ for increasing the next critical value $\alpha_{T}$. The rule (14) is
illustrated in Figure 3 below (see the blue line therein): in this experiment,
$F_{t}(\alpha_{t})=0$ for times $t\leq 36$, which entails that the sequence
$\alpha_{t}$ is actually increasing for $t\leq 36$, namely
$\alpha_{T}=\alpha\sum_{t=1}^{T}\gamma_{t}$, $T\leq 37$. This is admittedly
surprising for an online FWER controlling rule, but comes from the (strong)
discreteness of the tests. Note however that once the reward gets smaller, the
critical values fall shortly.

###  3.2 Smoothing out the super-uniformity reward

The greedy policy described in the previous section is not always appropriate
when time is considered on a potentially large period, because the sequence of
critical values might fall too abruptly. Instead, we can smooth this effect
over time, by distributing the reward collected at time $T-1$ overall times
following $T$. To formalize this idea, we introduce a SURE spending sequence
(see also Section 2.4), which is defined as a non-negative sequence
$\gamma^{\prime}=(\gamma^{\prime}_{t})_{t\geq 1}$ such that $\sum_{t\geq
1}\gamma^{\prime}_{t}\leq 1$. While this definition is mathematically
equivalent to the definition of a spending sequence, the role of the SURE
spending sequence is different, so we use a different name for it.

######  Definition 3.1.

For any spending sequence $\gamma$ and any SURE spending sequence
$\gamma^{\prime}$, the online Bonferroni procedure with super-uniformity
reward, denoted by
$\mathcal{A}^{\mbox{\tiny$\rho$OB}}=\\{\alpha^{\mbox{\tiny$\rho$OB}}_{t},t\geq
1\\}$, is defined by the recursion

$\alpha^{\mbox{\tiny$\rho$OB}}_{T}=\alpha\gamma_{T}+\sum_{t=1}^{T-1}\gamma^{\prime}_{T-t}\rho_{t},\quad
T\geq 1,$ (15)

where
$\rho_{t}=\alpha^{\mbox{\tiny$\rho$OB}}_{t}-F_{t}(\alpha^{\mbox{\tiny$\rho$OB}}_{t})$
denotes the super-uniformity reward at time $t$ for that procedure.

Note that taking $\gamma^{\prime}=(1,0,\dots 0)$ recovers the “greedy”
critical values (14). For the rectangular kernel SURE spending sequence given
by (9), we have
$\sum_{t=1}^{T-1}\gamma^{\prime}_{T-t}\rho_{t}=h^{-1}\sum_{t=1\vee(T-h)}^{T-1}\rho_{t}$,
which we interpret as a uniform spending of the SURE reward over the last $h$
time points. As shown in Figure 3, the corresponding sequence of critical
values is more “stable” than the one using the greedy approach, allowing for
some additional discoveries (as it is on this simulated data). The following
result provides FWER control of the new rewarded critical values (15), for a
general SURE spending sequence.

######  Theorem 3.1.

Consider the setting of Section 2.1, where a null bounding family
$\mathcal{F}=\\{F_{t},t\geq 1\\}$ satisfying (2) is at hand. For any spending
sequence $\gamma$ and any SURE spending sequence $\gamma^{\prime}$, consider
the online Bonferroni procedure $\mathcal{A}^{\mbox{\tiny
OB}}=\\{\alpha^{\mbox{\tiny OB}}_{t},t\geq 1\\}$ (10), and the online
Bonferroni with super-uniformity rewards
$\mathcal{A}^{\mbox{\tiny$\rho$OB}}=\\{\alpha^{\mbox{\tiny$\rho$OB}}_{t},t\geq
1\\}$ (15). Then we have
$\textnormal{FWER}(\mathcal{A}^{\mbox{\tiny$\rho$OB}},P)\leq\alpha$ for all
$P\in\mathcal{P}$, while $\mathcal{A}^{\mbox{\tiny$\rho$OB}}$ uniformly
dominates $\mathcal{A}^{\mbox{\tiny OB}}$.

This result will be a consequence of a more general result, see Section 3.4.

Figure 3: Sequences of critical values for Bonferroni procedures with
different rewards over time $1\leq t\leq T=300$ (simulated data): base
Bonferroni critical values (10) (orange line), rewarded with the greedy
approach (14) (blue line), and with the rectangular kernel SURE spending
sequence (15) ($h=100$, green line). The rug plots display the time of
discoveries for each procedure with the corresponding color. The grey dots
denote the $p$-value sequence. The $Y$-axis has been transformed by
$y\mapsto-\log(-\log(y))$. The spending sequence is $\gamma_{t}\propto
t^{-1.6}$.

###  3.3 Rewarded Adaptive Online Bonferroni

It is apparent from (11)-(12) that there is some looseness when upper-bounding
$\sum_{t\in\mathcal{H}_{0}}\gamma_{t}$ by $\sum_{t\geq 1}\gamma_{t}$ which may
lead to unnecessarily conservative procedures. We may attempt to avoid this
loss in efficiency by considering a spending sequence $\gamma$ satisfying the
condition $\sum_{t\in\mathcal{H}_{0}}\gamma_{t}\leq 1$ which is more liberal
than $\sum_{t\geq 1}\gamma_{t}\leq 1$. In words, this means that the index $t$
in the sequence $\\{\gamma_{t},t\geq 1\\}$ should only be incremented when we
are testing an hypothesis with $t\in\mathcal{H}_{0}$. Since $\mathcal{H}_{0}$
is unknown, such a modification cannot be implemented directly in the $\gamma$
sequence. Nevertheless, an approach proposed by Tian and Ramdas, (2021) works
by replacing the unknown set $\mathcal{H}_{0}$ by an estimate
$\\{1\\}\cup\\{t\geq 2\>:\>p_{t-1}\geq\lambda\\}$ for some parameter
$\lambda\in(0,1)$, and to correct the introduced error in the thresholds
$\alpha_{t}$ to maintain the FWER control. More formally, we follow Tian and
Ramdas, (2021) by introducing the re-indexation functional
$\mathcal{T}:\\{1,\dots\\}\to\\{1,\dots\\}$ defined by

$\displaystyle\mathcal{T}(T)=1+\sum_{t=2}^{T}{\mathbf{1}\\{p_{t-1}\geq\lambda\\}},\quad
T\geq 1.$ (16)

Since a large $p$-value is more likely to be linked to a true null,
$\mathcal{T}(T)$ is used to account for the number of true nulls before time
$T$ (note that this estimate is nevertheless biased). From an intuitive point
of view, $\mathcal{T}(T)$ slows down the time by only incrementing time when
the preceding $p$-value is large enough. This idea leads to the adaptive
online Bonferroni procedure (called there “Adaptive spending” 111The so-called
“discarding” part of the method proposed by Tian and Ramdas, (2021) cannot be
implemented in our setting because the $F_{t}$ are not convex, see also
Section 1.4.) introduced by Tian and Ramdas, (2021), with spending sequence
$\gamma$ and adaptivity parameter $\lambda\in[0,1)$, denoted here by
$\mathcal{A}^{\mbox{\tiny AOB}}=\\{\alpha^{\mbox{\tiny AOB}}_{t},t\geq 1\\}$,
and given by

$\displaystyle\alpha^{\mbox{\tiny
AOB}}_{T}=\alpha(1-\lambda)\gamma_{\mathcal{T}(T)},\quad T\geq 1.$ (17)

It recovers the standard online Bonferroni procedure when $\lambda=0$
($\mathcal{T}(T)=T$ for $T\geq 1$ in that case), but leads to different
thresholds when $\lambda>0$. Comparing $\mathcal{A}^{\mbox{\tiny AOB}}$ to
$\mathcal{A}^{\mbox{\tiny OB}}$, no procedure uniformly dominates the other.
An improvement of $\mathcal{A}^{\mbox{\tiny AOB}}$ over
$\mathcal{A}^{\mbox{\tiny OB}}$ is expected to hold when there are many false
null hypotheses in the data, and increasingly so if the signal occurs early in
the time sequence, see the numerical experiments in Section 5. In addition,
note that the critical value $\alpha^{\mbox{\tiny AOB}}_{T}$ depends on the
data $X_{1},\dots,X_{T-1}$ and thus is random. As a result, the adaptive
approach requires additional distributional assumptions compared with the
online Bonferroni procedure. In Tian and Ramdas, (2021),
$\mathcal{A}^{\mbox{\tiny AOB}}$ is proved to control the FWER under (1) and
(3) (actually under the slightly more general condition (4) with $F_{t}$ equal
to identity). Let us now use this approach in combination with the super-
uniformity reward.

######  Definition 3.2.

For any spending sequence $\gamma$ and any SURE spending sequence
$\gamma^{\prime}$, and $\lambda\in[0,1)$, the adaptive online Bonferroni
procedure with super-uniformity reward, denoted by
$\mathcal{A}^{\mbox{\tiny$\rho$AOB}}=\\{\alpha^{\mbox{\tiny$\rho$AOB}}_{t},t\geq
1\\}$, is defined by

$\alpha^{\mbox{\tiny$\rho$AOB}}_{T}=\alpha(1-\lambda)\gamma_{\mathcal{T}(T)}+\sum_{1\leq
t\leq T-1\atop
p_{t}\geq\lambda}\gamma^{\prime}_{T-t}\rho_{t}+\varepsilon_{T-1},\quad T\geq
1,$ (18)

where
$\rho_{t}=\alpha^{\mbox{\tiny$\rho$AOB}}_{t}-F_{t}(\alpha^{\mbox{\tiny$\rho$AOB}}_{t})$
denotes the super-uniformity reward a time $t$, and
$\varepsilon_{T-1}={\mathbf{1}\\{p_{T-1}<\lambda\\}}(\alpha_{T-1}-\alpha(1-\lambda)\gamma_{\mathcal{T}(T-1)})$
is an additional “adaptive” reward (convention $\varepsilon_{0}=0$).

This class of procedures reduces to the class of procedures (15) introduced in
the previous section by setting $\lambda=0$. However, when $\lambda>0$ the
class is different since the term $\alpha(1-\lambda)\gamma_{\mathcal{T}(T)}$,
which comes from $\alpha^{\mbox{\tiny AOB}}_{T}$, makes the threshold random.
Also, the super-uniformity reward is only collected at time $t\leq T-1$ where
$p_{t}\geq\lambda$. The latter is well expected from the motivation of the
adaptive approach described above: when $p_{t}<\lambda$, no testing is
performed so no reward could be obtained from $\rho_{t}$. Nevertheless, note
that the additional term $\varepsilon_{T-1}$ allows to collect some reward at
time $T-1$ in the case where $p_{T-1}<\lambda$. Since this term only appears
in critical values of adaptive procedures, we call it the “adaptive” reward.
It is linked to the super-uniformity reward in that no adaptive reward can be
obtained if no super-uniformity reward has been collected in the past. The
following result shows that this approach is valid from the FWER control
perspective.

######  Theorem 3.2.

Consider the setting of Section 2.1 where a null bounding family
$\mathcal{F}=\\{F_{t},t\geq 1\\}$ satisfying (2) is at hand. For any spending
sequence $\gamma$ and any SURE spending sequence $\gamma^{\prime}$ and
$\lambda\in[0,1)$, consider the adaptive online Bonferroni procedure
$\mathcal{A}^{\mbox{\tiny AOB}}=\\{\alpha^{\mbox{\tiny AOB}}_{t},t\geq 1\\}$
(17) and the adaptive online Bonferroni with super-uniformity rewards
$\mathcal{A}^{\mbox{\tiny$\rho$AOB}}=\\{\alpha^{\mbox{\tiny$\rho$AOB}}_{t},t\geq
1\\}$ (18). Then, assuming that the model $\mathcal{P}$ is such that (3)
holds, we have
$\textnormal{FWER}(\mathcal{A}^{\mbox{\tiny$\rho$AOB}},P)\leq\alpha$ for all
$P\in\mathcal{P}$, while $\mathcal{A}^{\mbox{\tiny$\rho$AOB}}$ uniformly
dominates $\mathcal{A}^{\mbox{\tiny AOB}}$.

Theorem 3.2 relies on a more general result (Theorem 3.3 below). Note that,
contrary to Theorem 3.1, Theorem 3.2 needs an independence assumption. This
was already the case without the super-uniformity reward since this is due to
the adaptive methodology that makes the critical values random. If this
independence assumption holds, we show in Section 5 that
$\mathcal{A}^{\mbox{\tiny$\rho$AOB}}$ can indeed improve
$\mathcal{A}^{\mbox{\tiny$\rho$OB}}$, while it always improves the procedure
$\mathcal{A}^{\mbox{\tiny AOB}}$ of Tian and Ramdas, (2021) (as guaranteed by
the above theorem).

###  3.4 Rewarded version for base FWER controlling procedures

In this section we present a general result stating that any procedure
ensuring online FWER control (in a specific way) can be rewarded using super-
uniformity while maintaining the FWER control.

######  Theorem 3.3.

Assuming that (2) holds, consider any procedure
$\mathcal{A}^{0}=(\alpha^{0}_{t},t\geq 1)$ satisfying almost surely, for some
$\lambda\in[0,1)$ and for all $T\geq 1$,

$\displaystyle\alpha^{0}_{T}+\sum_{1\leq t\leq T-1,\atop
p_{t}\geq\lambda}\alpha^{0}_{t}\leq(1-\lambda)\alpha.$ (19)

Then the following holds:

  * (i)

$\mathcal{A}^{0}$ controls the online FWER, that is,
$\textnormal{FWER}(\mathcal{A}^{0},P)\leq\alpha$ for all $P\in\mathcal{P}$,
either if the $\alpha^{0}_{T}$ are deterministic for all $T\geq 1$, or if (3)
holds;

  * (ii)

for any SURE spending sequence $\gamma^{\prime}=(\gamma^{\prime}_{t},t\geq
1)$, the procedure $\mathcal{A}=(\alpha_{t},t\geq 1)$, corresponding to the
rewarded $\mathcal{A}^{0}$, and defined by

$\displaystyle{\alpha}_{T}=\alpha^{0}_{T}+\sum_{1\leq t\leq T-1\atop
p_{t}\geq\lambda}\gamma^{\prime}_{T-t}({\alpha}_{t}-F_{t}({\alpha}_{t}))+{\mathbf{1}\\{p_{T-1}<\lambda\\}}({\alpha}_{T-1}-\alpha^{0}_{T-1}),\quad
T\geq 1,$ (20)

controls the online FWER, that is,
$\textnormal{FWER}(\mathcal{A},P)\leq\alpha$ for all $P\in\mathcal{P}$, either
if the $\alpha_{T}$ are deterministic for all $T\geq 1$, or if (3) holds.

Theorem 3.3 is proved in Section A.1. Condition (19) is essentially the same
as Condition (20) derived in Tian and Ramdas, (2021). It is satisfied by the
online Bonferroni procedure ($\mathcal{A}^{0}=\mathcal{A}^{\mbox{\tiny OB}}$),
and the online adaptive Bonferroni procedure
($\mathcal{A}^{0}=\mathcal{A}^{\mbox{\tiny AOB}}$). While this is obvious for
$\mathcal{A}^{\mbox{\tiny OB}}$, the case of $\mathcal{A}^{\mbox{\tiny AOB}}$
requires to carefully check how the functional $\mathcal{T}(\cdot)$ (16) slows
down the time, which is done in Lemma A.3. Statement (i) of Theorem 3.3 thus
proves the online FWER control for these procedures. Statement (ii) of Theorem
3.3 is our main contribution and reduces to Theorems 3.1 and 3.2, when
choosing $\mathcal{A}^{0}=\mathcal{A}^{\mbox{\tiny OB}}$ and
$\mathcal{A}^{0}=\mathcal{A}^{\mbox{\tiny AOB}}$, respectively. This recovers
the rewarded procedures $\mathcal{A}^{\mbox{\tiny$\rho$OB}}$ and
$\mathcal{A}^{\mbox{\tiny$\rho$AOB}}$ found in the previous sections: compare
(20) to (15) (with $\lambda=0$), and (20) to (18). Nevertheless, other choices
for $\mathcal{A}^{0}$ satisfying (19) are possible. According to our general
result, any such choice is compatible with our rewarding methodology.

##  4 Online mFDR control

In this section, we aim at finding procedures $\mathcal{A}$ such that
$\textnormal{mFDR}(\mathcal{A},P)\leq\alpha$ for some targeted level
$\alpha\in(0,1)$. We follow the same route as for the FWER: we start with an
application of the super-uniformity reward to the classical LORD++ procedure
(Ramdas et al.,, 2017, called just LORD hereafter for short), and then turn to
adaptive counterparts. Finally, we propose a general result encompassing all
these cases. In this section, we follow the notation of Ramdas et al., (2017)
for online mFDR control. For any procedure $\mathcal{A}=\\{\alpha_{t},t\geq
1\\}$ and realization of the $p$-value process, let us denote

$R(T)=\sum_{t=1}^{T}{\mathbf{1}\\{p_{t}(X_{t})\leq\alpha_{t}\\}}$ (21)

the number of rejections of the procedure up to time $T$, and

$\tau_{j}=\min\\{t\geq 1\>:\>R(t)\geq j\\}\>\>\>\mbox{ ($\tau_{j}=+\infty$ if
the set is empty)},$ (22)

the first time that the procedure makes $j$ rejections, for any $j\geq 1$.

###  4.1 Warming up: LORD procedure and a first greedy reward

While a sufficient condition for online FWER control is $\sum_{t\geq
1}\alpha_{t}\leq\alpha$ (see the previous section and in particular (19)), the
mFDR control is ensured when $\sum_{t\geq 1}\alpha_{t}\leq\alpha(1\vee R(T))$,
as proved in Theorem 2 of Ramdas et al., (2017) (applicable, e.g., under
assumptions (2) and (3)). Consequently, for each rejection we earn back wealth
$\alpha$ with which we are allowed to increase $\alpha_{t}$; typically by
starting a new online Bonferroni critical value process. This idea is referred
to as $\alpha$-investing in the literature, see Foster and Stine, (2008);
Aharoni and Rosset, (2014); Javanmard and Montanari, (2018). This idea leads
to the LORD (Levels based On Recent Discovery) procedure (Javanmard and
Montanari,, 2018), with the improvement given by Ramdas et al., (2017):

$\displaystyle\alpha^{\mbox{\tiny LORD}}_{T}=W_{0}\gamma_{T}+(\alpha-
W_{0})\gamma_{T-\tau_{1}}+\alpha\sum_{j\geq 2}\gamma_{T-\tau_{j}},\quad T\geq
1,$ (23)

where by convention $\gamma_{t}=0$ at any time $t\leq 0$ and where $\gamma$ is
an arbitrary spending sequence. Note that the test level at time $T$ splits
the initial $\alpha$-wealth between the cases where $R(T)=0$ and $R(T)=1$,
because the bound is equal to $\alpha(1\vee R(T))=\alpha$ in both cases so the
first rejection does not provide an extra room for false discoveries. The
resulting additional parameter $W_{0}\in(0,\alpha)$ balances the initial
$\alpha$-wealth between these two cases to maintain the mFDR control. The
procedure $\mathcal{A}^{\mbox{\tiny LORD}}=\\{\alpha^{\mbox{\tiny
LORD}}_{t},t\geq 1\\}$ controls the mFDR under (1) and (3), because
$\sum_{t\geq 1}\alpha^{\mbox{\tiny LORD}}_{t}\leq\alpha(1\vee R(T))$ (see
Appendix A.2 for a proof). Now, let us consider our more general framework
where we have at hand a null bounding family $\mathcal{F}=\\{F_{t},t\geq 1\\}$
satisfying (2). In that case, we can prove that a sufficient condition on the
critical values for mFDR control is that, almost surely,

$\displaystyle\sum_{t=1}^{T}F_{t}(\alpha_{t})\leq\alpha_{T}+\sum_{t=1}^{T-1}F_{t}(\alpha_{t})\leq\alpha(1\vee
R(T)),$

see the general condition (34) below. This can be achieved by choosing

$\displaystyle\alpha_{T}=\sum_{t=1}^{T}\alpha^{\mbox{\tiny
LORD}}_{t}-\sum_{t=1}^{T-1}F_{t}(\alpha_{t}),\quad T\geq 1.$

This leads to the thresholds

$\displaystyle\alpha_{T}=\alpha^{\mbox{\tiny LORD}}_{T}+\rho_{T-1},\quad T\geq
1,$ (24)

where $\rho_{T-1}=\alpha_{T-1}-F_{T-1}(\alpha_{T-1})$ is the super-uniformity
reward (8) at time $T-1$ (with the convention $\rho_{0}=0$). Since
$\rho_{t}\geq 0$ for all $t$ by (2), this procedure uniformly dominates the
procedure $\mathcal{A}^{\mbox{\tiny LORD}}$. Furthermore, depending on the
magnitude of the super-uniformity reward, this new procedure is potentially
much more powerful.

Figure 4: Sequences of critical values of LORD procedure with different
rewards over time $1\leq t\leq T=300$ (simulated data): base LORD critical
values (23)(orange line), rewarded with the greedy approach (24) (blue line),
and with the rectangular kernel SURE spending sequence (25) ($h=10$, green
line). The rug plots display the time of discoveries for each procedure with
the corresponding color. The grey dots denote the $p$-value sequence. The
$y$-axis has been transformed by $y\mapsto-\log(-\log(y))$. The spending
sequence is $\gamma_{t}\propto t^{-1.6}$.

###  4.2 Smoothing out the super-uniformity reward

As discussed for FWER control (see Section 3.2), the preliminary procedure
(24) spends immediately at time $T$ all of the super-uniformity reward
collected at time $T-1$. However, it is more advantageous to redistribute this
reward over subsequent times $T,T+1,\dots$, by using a SURE spending sequence
$\gamma^{\prime}=(\gamma^{\prime}_{t})_{t\geq 1}$. This gives rise to the
following more general class of online procedures.

######  Definition 4.1.

For a spending sequence $\gamma$ and a SURE spending sequence
$\gamma^{\prime}$, the LORD procedure with super-uniformity reward, denoted by
$\mathcal{A}^{\mbox{\tiny$\rho$LORD}}=\\{\alpha^{\mbox{\tiny$\rho$LORD}}_{t},t\geq
1\\}$, is defined by the recursion

$\alpha^{\mbox{\tiny$\rho$LORD}}_{T}=\alpha^{\mbox{\tiny
LORD}}_{T}+\sum_{t=1}^{T-1}\gamma^{\prime}_{T-t}\rho_{t}\quad T\geq 1,$ (25)

where $\alpha^{\mbox{\tiny LORD}}_{T}$ is given by (23) and
$\rho_{t}=\alpha^{\mbox{\tiny$\rho$LORD}}_{t}-F_{t}(\alpha^{\mbox{\tiny$\rho$LORD}}_{t})$
denotes the super-uniformity reward at time $t$.

Figure 4 displays the critical values of the LORD procedure, and of those
rewarded with the greedy SURE spending sequence $\gamma^{\prime}=(1,0,\dots)$
or rewarded by the rectangular kernel SURE spending sequence (25) ($h=10$).
First, the reward given by the $\alpha$-investing, which is possible for mFDR
control, is visible at each discovery for which all critical value curves
“jump”. Second, the effect of the super-uniformity reward is visible between
these jumps, and the kernel sequence is able to better smooth the critical
value sequence. As a result, the corresponding procedure is more likely to
make more discoveries (as it is the case on the simulated data presented in
Figure 4). The following result establishes the mFDR control of this new class
of rewarded online procedures.

######  Theorem 4.1.

Consider the setting of Section 2.1 where a null bounding family
$\mathcal{F}=\\{F_{t},t\geq 1\\}$ satisfying (2) is at hand. For any spending
sequence $\gamma$ and any SURE spending sequence $\gamma^{\prime}$, consider
the LORD procedure $\mathcal{A}^{\mbox{\tiny LORD}}=\\{\alpha^{\mbox{\tiny
LORD}}_{t},t\geq 1\\}$ (23) and the LORD procedure with super-uniformity
rewards
$\mathcal{A}^{\mbox{\tiny$\rho$LORD}}=\\{\alpha^{\mbox{\tiny$\rho$LORD}}_{t},t\geq
1\\}$ (25). Then, assuming that the model $\mathcal{P}$ is such that (3)
holds, we have
$\textnormal{mFDR}(\mathcal{A}^{\mbox{\tiny$\rho$LORD}},P)\leq\alpha$ for all
$P\in\mathcal{P}$ while $\mathcal{A}^{\mbox{\tiny$\rho$LORD}}$ uniformly
dominates $\mathcal{A}^{\mbox{\tiny LORD}}$.

This theorem is proved in Section A.2, as a corollary of a more general result
(Theorem 4.3 below). As shown in the numerical experiments (Section 5), the
improvement of $\mathcal{A}^{\mbox{\tiny$\rho$LORD}}$ with respect to
$\mathcal{A}^{\mbox{\tiny LORD}}$ can be substantial.

###  4.3 Rewarded Adaptive LORD

In this section, we apply the re-indexation trick of the $\gamma$ sequence
presented in Section 3.3 to improve the performance of the procedures
$\mathcal{A}^{\mbox{\tiny LORD}}$ and $\mathcal{A}^{\mbox{\tiny$\rho$LORD}}$.
For this, we follow essentially the reasoning used by Ramdas et al., 2018b
for deriving the SAFFRON procedure, with a slight modification, as explained
below. To start, let us define, for some parameter $\lambda\in[0,1)$,

$\displaystyle\mathcal{T}_{j}(T)=\left\\{\begin{array}[]{ll}1+\sum_{t=\tau_{j}+2}^{T}{\mathbf{1}\\{p_{t-1}\geq\lambda\\}}&\mbox{
if $T\geq\tau_{j}+1$ }\\\ 0&\mbox{ if $T\leq\tau_{j}$}\end{array}\right.,\quad
j\geq 1,$ (28)

with $\mathcal{T}_{0}(T)=\mathcal{T}(T)$ given by (16) by convention. As
illustrated in Figure 5, $\mathcal{T}_{j}(T)$ is like a “stopwatch” starting
after $\tau_{j}$ and suspended at each time $t$ for which $p_{t-1}<\lambda$.
Hence, having $p_{t}<\lambda$ allows to delay the natural dissipation of
$\alpha$-wealth due to online testing.

$p_{t}<\lambda$ | $\bullet$ | $\bullet$ | $\circ$ | $\circ$ | $\bullet$ | $\circ$ | $\circ$ | $\bullet$ | $\circ$
---|---|---|---|---|---|---|---|---|---
$p_{t}\leq\alpha_{t}$ | $\circ$ | $\circ$ | $\circ$ | $\bullet$ | $\circ$ | $\circ$ | $\circ$ | $\bullet$ | $\bullet$
$t$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$
$\mathcal{T}_{0}(t)$ | $1$ | $1$ | $1$ | $2$ | $3$ | $3$ | $4$ | $5$ | $5$
$\mathcal{T}_{1}(t)$ | $0$ | $0$ | $0$ | $0$ | $1$ | $1$ | $2$ | $3$ | $3$
$\mathcal{T}_{2}(t)$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $1$
Figure 5: Illustration for the time re-indexation functionals
$\mathcal{T}_{j}(T)$ given by (28). Here, $\tau_{1}=4$, $\tau_{2}=8$,
$\tau_{3}=9$. The symbol “$\bullet$” (resp. “$\circ$”) codes for “true” (resp.
“not true”).

Then, the SAFFRON procedure Ramdas et al., 2018b  is defined by the threshold

$\displaystyle\alpha_{T}=\min\left(\lambda,(1-\lambda)\left(W_{0}\gamma_{\mathcal{T}_{0}(T)}+(\alpha-
W_{0})\gamma_{\mathcal{T}_{1}(T)}+\alpha\sum_{j\geq
2}\gamma_{\mathcal{T}_{j}(T)}\right)\right).$ (29)

This procedure controls the mFDR under (1) and (3) as proved by Ramdas et al.,
2018b . However, examining the proof in Ramdas et al., 2018b , it turns out
that the capping with $\lambda$ is not necessary. The capping prevents the
critical values from exceeding $\lambda$, thus avoiding to get
$p_{t}\geq\lambda$ when $p_{t}\leq\alpha_{t}$. However, to our knowledge, the
latter does not play any role in the mFDR control, and we work with the
(uniformly dominating) procedure

$\alpha^{\mbox{\tiny
ALORD}}_{T}=(1-\lambda)\left(W_{0}\gamma_{\mathcal{T}_{0}(T)}+(\alpha-
W_{0})\gamma_{\mathcal{T}_{1}(T)}+\alpha\sum_{j\geq
2}\gamma_{\mathcal{T}_{j}(T)}\right).$ (30)

With the capping (29), an mFDR control is provided in Theorem 1 in Ramdas et
al., 2018b . For our version (30), the mFDR control follows as a special case
of Theorem 4.2 below with $F_{t}(u)=u$ for all $t,u$. Also note that
$\mathcal{A}^{\mbox{\tiny ALORD}}$ reduces to $\mathcal{A}^{\mbox{\tiny
LORD}}$ (23) when $\lambda=0$, because $\mathcal{T}_{j}(T)=0\vee(T-\tau_{j})$
in that case. Now, we generalize this method to our present framework.

######  Definition 4.2.

For a spending sequences $\gamma$, a SURE spending sequence $\gamma^{\prime}$
and $\lambda\in[0,1)$, the adaptive LORD procedure with super-uniformity
reward denoted by
$\mathcal{A}^{\mbox{\tiny$\rho$ALORD}}=\\{\alpha^{\mbox{\tiny$\rho$ALORD}}_{t},t\geq
1\\}$, is defined by

$\alpha^{\mbox{\tiny$\rho$ALORD}}_{T}=\alpha^{\mbox{\tiny
ALORD}}_{T}+\sum_{1\leq t\leq T-1\atop
p_{t}\geq\lambda}\gamma^{\prime}_{T-t}\rho_{t}+\varepsilon_{T-1},\quad T\geq
1,$ (31)

where $\alpha^{\mbox{\tiny ALORD}}_{T}$ is defined by (30),
$\rho_{t}=\alpha^{\mbox{\tiny$\rho$ALORD}}_{t}-F_{t}(\alpha^{\mbox{\tiny$\rho$ALORD}}_{t})$
denotes the super-uniformity reward a time $t$ and
$\varepsilon_{T-1}={\mathbf{1}\\{p_{T-1}<\lambda\\}}(\alpha^{\mbox{\tiny$\rho$ALORD}}_{T-1}-\alpha^{\mbox{\tiny
ALORD}}_{T-1})$ is an additional “adaptive” reward at time $T-1$ (convention
$\varepsilon_{0}=0$).

Note that $\mathcal{A}^{\mbox{\tiny$\rho$ALORD}}$ reduces to
$\mathcal{A}^{\mbox{\tiny$\rho$LORD}}$ (25) when $\lambda=0$, and to
$\mathcal{A}^{\mbox{\tiny ALORD}}$ when $F_{t}(u)=u$ for all $u,t$. The
following result shows that this class of procedures controls the mFDR.

######  Theorem 4.2.

Consider the setting of Section 2.1 where a null bounding family
$\mathcal{F}=\\{F_{t},t\geq 1\\}$ satisfying (2) is at hand. For any spending
sequence $\gamma$ and any SURE spending sequence $\gamma^{\prime}$, consider
the adaptive LORD procedure $\mathcal{A}^{\mbox{\tiny
ALORD}}=\\{\alpha^{\mbox{\tiny ALORD}}_{t},t\geq 1\\}$ (30), and the adaptive
LORD procedure with super-uniformity rewards
$\mathcal{A}^{\mbox{\tiny$\rho$ALORD}}=\\{\alpha^{\mbox{\tiny$\rho$ALORD}}_{t},t\geq
1\\}$ (31). Then, assuming that the model $\mathcal{P}$ is such that (3)
holds, we have
$\textnormal{mFDR}(\mathcal{A}^{\mbox{\tiny$\rho$ALORD}},P)\leq\alpha$ for all
$P\in\mathcal{P}$ while $\mathcal{A}^{\mbox{\tiny$\rho$ALORD}}$ uniformly
dominates $\mathcal{A}^{\mbox{\tiny ALORD}}$ and thus also the SAFFRON
procedure of Ramdas et al., 2018b .

Theorem 4.2 follows from Theorem 4.3 below. Let us underline that
$\mathcal{A}^{\mbox{\tiny$\rho$ALORD}}$ both incorporates $\alpha$-investing
and super-uniformity reward. Thus, it is expected to be the most powerful
among the procedures considered in the present paper. This is supported both
by the numerical experiments of Section 5 and the real data analysis in
Section 6.

###  4.4 Rewarded version for base mFDR controlling procedures

The following result establishes that any base online mFDR controlling
procedure (of a specific type) can be rewarded with super-uniformity.

######  Theorem 4.3.

Assuming that both (2) and (3) hold, consider any procedure
$\mathcal{A}^{0}=(\alpha^{0}_{t},t\geq 1)$ satisfying almost surely, for some
$\lambda\in[0,1)$ and for all $T\geq 1$,

$\displaystyle\alpha^{0}_{T}+\sum_{1\leq t\leq T-1,\atop
p_{t}\geq\lambda}\alpha^{0}_{t}\leq(1-\lambda)\alpha\>(1\vee R(T)),$ (32)

where $R(T)$ denotes the number of rejections up to time $T$ for this
procedure, see (21). Then the following holds

  * (i)

$\mathcal{A}^{0}$ controls the online mFDR, that is,
$\textnormal{mFDR}(\mathcal{A}^{0},P)\leq\alpha$ for all $P\in\mathcal{P}$;

  * (ii)

for any SURE spending sequence $\gamma^{\prime}=(\gamma^{\prime}_{t},t\geq
1)$, the procedure $\mathcal{A}=(\alpha_{t},t\geq 1)$, corresponding to the
rewarded $\mathcal{A}^{0}$, and defined by (20), controls the online mFDR,
that is, $\textnormal{mFDR}(\mathcal{A},P)\leq\alpha$ for all
$P\in\mathcal{P}$.

Theorem 4.3 is proved in Section A.2. Condition (32) is essentially the same
as the condition found in Theorem 1 of Ramdas et al., 2018b . Our main
contribution is thus in statement (ii), showing that the super-uniformity
reward can be used with any base procedure $\mathcal{A}^{0}$ satisfying (32).
Since the latter condition holds for the LORD procedure
$\mathcal{A}^{0}=\mathcal{A}^{\mbox{\tiny LORD}}$, and the adaptive LORD
procedure $\mathcal{A}^{0}=\mathcal{A}^{\mbox{\tiny ALORD}}$ (see Lemma A.3),
Theorem 4.3 entails Theorem 4.1 and Theorem 4.2, respectively. Finally, let us
emphasize the similarity between Theorem 3.3 (FWER) and Theorem 4.3 (mFDR).
Strikingly, the reward takes exactly the same form (20), which makes the range
of improvement comparable for these two criteria.

##  5 Numerical results

In this section, we study the performances of our newly derived SURE
procedures in a discrete online multiple testing problem. For space reasons,
we defer some of the numerical results in Appendix B.

###  5.1 Considered procedures

The considered procedures are the base (non-rewarded) procedures
$\mathcal{A}^{\mbox{\tiny OB}}$ (10), $\mathcal{A}^{\mbox{\tiny AOB}}$ (17),
$\mathcal{A}^{\mbox{\tiny LORD}}$ (23), and $\mathcal{A}^{\mbox{\tiny ALORD}}$
(30), and their rewarded counterparts $\mathcal{A}^{\mbox{\tiny$\rho$OB}}$
(18), $\mathcal{A}^{\mbox{\tiny$\rho$AOB}}$ (18),
$\mathcal{A}^{\mbox{\tiny$\rho$LORD}}$ (31), and
$\mathcal{A}^{\mbox{\tiny$\rho$ALORD}}$ (31) respectively. As mentioned in
Section 1.4, we also consider the ADDIS-spending and ADDIS procedures (see
Tian and Ramdas,, 2021, 2019) although the type I error rate control is not
guaranteed for these two procedures, in our (discrete) setting. The parameters
of the OMT are set to $\alpha=0.2$, $W_{0}=\alpha/2$ and $\lambda=0.5$. For
ADDIS and ADDIS-spending, we use the default values
$W_{0}=\frac{\alpha\lambda\tau}{2}$, with $\lambda=0.25$ and $\tau=0.5$ (the
latter being the discarding parameter, see Tian and Ramdas,, 2021, 2019).
Following Tian and Ramdas, (2019), we set $\gamma_{t}\propto t^{-1.6}$ with a
normalizing constant chosen such that $\sum_{t=1}^{+\infty}\gamma_{t}=1$. For
the SURE spending sequence $(\gamma^{\prime}_{t})_{t\geq 1}$ we use a
rectangular kernel with bandwidth $h$, as defined by (9), with $h=100$ for
FWER and $h=10$ for mFDR. We discuss different choices for tuning parameters
in the SURE procedures (adaptivity parameter $\lambda$ and the rectangular
kernel bandwidth $h$) in Appendices B.3 and B.4.

###  5.2 Simulation setting

We simulate $m$ experiments in which the goal is to detect differences between
two groups by counting the number of successes/failures in each group. More
specifically, we follow Gilbert, 2005b , Heller and Gur, (2011) and Döhler et
al., (2018) by simulating a two-sample problem in which a vector of $m$
independent binary responses (e.g., “a click is made” in the web design A/B
testing example) is observed for $N$ subjects in both groups. The goal is to
test the $m$ null hypotheses $H_{0i}$: “$p_{1i}=p_{2i}$”, $i=1,...,m$ in an
online fashion, where $p_{1i}$ and $p_{2i}$ are the success probabilities for
the $i^{th}$ binary response in group A and B respectively. Thus, for each
hypothesis $i$, the data can be summarized by a $2\times 2$ contingency table,
and we use (two-sided) Fisher’s exact test for testing $H_{0i}$. The $m$
hypotheses are split in three groups of size $m_{1}$, $m_{2}$, and $m_{3}$
such that $m=m_{1}+m_{2}+m_{3}$. Then, the binary responses are generated as
iid Bernoulli of probability 0.01 ($\mathcal{B}(0.01)$) at $m_{1}$ positions
for both groups, iid $\mathcal{B}(0.10$) at $m_{2}$ positions for both groups,
and iid $\mathcal{B}(0.10)$ at $m_{3}$ positions for one group and iid
$\mathcal{B}(p_{3})$ at $m_{3}$ positions for the other group. Thus, the null
hypotheses are true for $m_{1}+m_{2}$ positions (set $\mathcal{H}_{0}$), while
the null hypotheses are false for $m_{3}$ positions (set $\mathcal{H}_{1}$).
Therefore, we interpret $p_{3}$ as the strength of the signal while
$\pi_{A}=\frac{m_{3}}{m}$, corresponds to the proportion of signal. Also,
$m_{1}$ and $m_{2}$ are both taken equal to $\frac{m-m_{3}}{2}$. In these
experiments, we fix $m=500$, and vary each one of the parameters
$\mathcal{H}_{1}$ (Section 5.3), $\pi_{A}$ (Section 5.4), $N$ (Appendix B.1),
$p_{3}$ (Appendix B.2) while keeping the others fixed. The default values are
$\pi_{A}=0.3$, $N=25$, $p_{3}=0.4$ and $\mathcal{H}_{1}\subset\\{1,\dots,m\\}$
chosen randomly for each simulation run. We estimate the different criteria
(FWER (LABEL:eq:DefFWER), mFDR (6), power (7)) using empirical mean over 10
000 independent simulation trials.

###  5.3 Position of signal

We start by studying how the position of the signal can affect the
performances of the procedures (it is well-known to be crtitical, see Foster
and Stine,, 2008; Ramdas et al.,, 2017). We investigate different positioning
schemes in which the signal can be clustered at the beginning of the stream,
or at the end, or clustered between the two, as described in the caption of
Figure 6.

|
---|---
Figure 6: Power and type I error rates of the different considered OMT versus
positions of the signal: at the beginning (B), the end (E), half at the
beginning and half in the middle of the stream (BM), half at the beginning and
half at the end of the stream (BE), half in the middle and half at the end of
the stream (ME), and taken uniformly at random (Random).

Consistently with our theoretical results, Figure 6 shows that all procedures
control the type I error rate at level $\alpha=0.2$. In terms of power, we can
see that the rewarded procedures have greater power than the associated base
procedures. More specifically, $\mathcal{A}^{\mbox{\tiny$\rho$ALORD}}$
uniformly dominates the other procedures for mFDR control and
$\mathcal{A}^{\mbox{\tiny$\rho$AOB}}$ for FWER control. The gain in power is
most noticeable when the signal is not localized at the beginning of the
stream (i.e. positions ME, E, and Random) for which the online testing problem
is more difficult. These first results indicate that the rewarded procedures
may protect against “$\alpha$-death”.

###  5.4 Proportion of signal

Figure 7 displays the results for $\pi_{A}$ varying in $\\{0.1,\dots,1\\}$. It
shows that the aforementioned superiority of the rewarded procedures holds in
this whole range. Also note that the SURE reward can affect the monotonicity
of the power curves: while most curves are increasing with $\pi_{A}$, the
power of the rewarded procedure $\mathcal{A}^{\mbox{\tiny$\rho$OB}}$
decreases. An explanation could be that when $\pi_{A}$ increases, the marginal
counts increase, and thus the degree of discreteness decreases providing a
smaller super-uniformity reward. However, using adaptivity seems to compensate
for this effect, thus providing better results.

|
---|---
Figure 7: Power and type I error rates of the considered procedures for
$\pi_{A}\in\\{0.1,0.2,\ldots,0.9,1\\}$.

Finally, let us mention that the additional numerical results in Appendix B
provide qualitatively similar conclusions for all other explored parameter
configurations: the SURE procedures $\mathcal{A}^{\mbox{\tiny$\rho$AOB}}$ and
$\mathcal{A}^{\mbox{\tiny$\rho$ALORD}}$ always improve, sometimes
substantially, the existing OMT.

##  6 Application to IMPC data

In this section we analyse data from the International Mouse Phenotyping
Consortium (IMPC), which coordinates studies on the genotype influence on
mouse phenotype. More precisely, scientists test the hypotheses that the
knock-out of certain genes will not change certain phenotypic traits (e.g.,
the coat or eye color). Since the dataset is constantly evolving as new genes
are studied for new phenotypic traits of interest, online multiple testing is
a natural approach for analysing such data, see also Tian and Ramdas, (2021);
Xu and Ramdas, (2021). We use the dataset provided by Karp et al., (2017)
which includes, for each studied gene, the count of normal and abnormal
phenotype for female and male mice (separately), thus providing two by two
contingency tables, which can be analysed by using Fisher Exact Tests (FETs).
In this section, we investigate the genotype effect on the phenotype
separately for male and female. The dataset originally contains nearly
$270\,000$ genes studies, but we focus on the first $30\,000$ genes for
simplicity. We set the global level $\alpha$ to $0.2$ and $0.05$, respectively
for FWER and mFDR procedures. For the procedure parameters, we follow the
choice made in the simulation part (Section 5): we set $\lambda$ to $0.5$ and
$W_{0}$ to $\alpha(1-\lambda)$ for mFDR procedures. We use the spending
sequence $\gamma_{t}\propto t^{-1.6}$ (with a normalizing constant chosen such
that $\sum_{t=1}^{+\infty}\gamma_{t}=1$). For the SURE spending sequence
$(\gamma^{\prime}_{t})_{t\geq 1}$ we use a rectangular kernel with bandwidth
$h$, as defined by (9) (with $h=100$ for FWER and $h=10$ for mFDR). Table 3
presents the number of discoveries for the FWER controlling procedures OB,
AOB, $\rho$OB, $\rho$AOB (left) and for the mFDR controlling procedures LORD,
ALORD, $\rho$LORD, $\rho$ALORD (right). The results show that ignoring the
discreteness of the tests causes the scientist to miss (potentially many)
discoveries. Hence, using the SURE methods helps to reduce this risk.

Procedures | OB |  $\rho$OB | AOB |  $\rho$AOB | LORD |  $\rho$LORD | ALORD |  $\rho$ALORD
---|---|---|---|---|---|---|---|---
$\\#$ discoveries (male) | 229 | 377 | 281 | 697 | 882 | 972 | 972 | 1041
$\\#$ discoveries (female) | 267 | 481 | 764 | 811 | 839 | 946 | 966 | 1046
Table 3: Number of discoveries for the FWER controlling OMT procedures (left)
and mFDR controlling OMT procedures (right), for male (second row) and female
(third row) mice in the IMPC data. These numbers are obtained by running the
OMT on the first $30\,000$ genes.

Figure 8 (FWER procedures) and Figure 9 (mFDR procedures) illustrate in more
detail how the super-uniformity reward leads to more discoveries, in the case
of male mice (similar findings hold for the female mice for which the
corresponding figures can be found in Appendix C.2). First, note that the
smallest $p$-values occur at the beginning of the stream (see Figure 14 in
Appendix C.1), so that we limit the visual analysis to the first $1500$
$p$-values for clarity of exposition. For the $\rho$OB procedure, the benefit
of incorporating the super-uniformity reward is visible in the left panel of
Figure 8. As expected from Figure 3, applying a rectangular kernel to these
rewards yields a smooth curve. For the $\rho$AOB procedure, presented in the
right panel of Figure 8, the improvement is even stronger, but the resulting
critical value curve is less smooth. This is due to the “adaptive” reward,
that is, the $\varepsilon_{T-1}$-component of our improvement, recall (18).
More precisely, an explanation of this “saw-tooth” shape is that during a
period with $p$-values smaller than $\lambda$, we have
$\alpha^{\mbox{\tiny$\rho$AOB}}_{T}-\alpha^{\mbox{\tiny
AOB}}_{T}\geq\alpha^{\mbox{\tiny$\rho$AOB}}_{T-1}-\alpha^{\mbox{\tiny
AOB}}_{T-1}$ so the gain increases. Also, if this period lasts for a while (as
for $500\lesssim t\lesssim 1240$ here), the $\rho$-part of the reward vanishes
and we end up with a constant gain
$\alpha^{\mbox{\tiny$\rho$AOB}}_{T}-\alpha^{\mbox{\tiny
AOB}}_{T}\approx\alpha^{\mbox{\tiny$\rho$AOB}}_{T-1}-\alpha^{\mbox{\tiny
AOB}}_{T-1}$, explaining the flat part of the curve, until the next
$p_{T}\geq\lambda$ occurs. After this point, we switch from the
$\varepsilon$-regime back to the $\rho$-regime, i.e.,
$\alpha^{\mbox{\tiny$\rho$AOB}}_{T+1}=\alpha^{\mbox{\tiny
AOB}}_{T+1}+\gamma^{\prime}_{1}\rho_{T}$. Since typically
$\gamma^{\prime}_{1}\rho_{T}\ll\alpha^{\mbox{\tiny$\rho$AOB}}_{T-1}-\alpha^{\mbox{\tiny
AOB}}_{T-1}$, this causes the downward jump in the green curve. For the mFDR
procedures presented in Figure 9, there is an additional “rejection” reward as
described in Section 4. Note that this makes some critical values exceed $1$,
which thus cannot be displayed in the $Y$-axis scale considered in that
figure. However, these values are still used in the OMT algorithms to compute
the future critical values. The obtained results are qualitatively similar to
the FWER setting: our proposed reward makes the green curves run above the
orange ones, uniformly over the considered time, hence inducing significantly
more discoveries.

|
---|---
Figure 8: Applying online FWER controlling procedures to the male mice IMPC data set. Left panel: $p$-values and critical values for OB (orange curve) and $\rho$OB (green curve). Right panel: AOB (orange curve) and $\rho$AOB (green curve). Representation similar to Figure 3.  |
---|---
Figure 9: Applying online mFDR controlling procedures to the male mice IMPC
data set. Left panel: $p$-values and critical values for LORD (orange curve)
and $\rho$LORD (green curve). Right panel: ALORD (orange curve) and
$\rho$ALORD (green curve). Representation similar to Figure 4.

##  7 Conclusion and discussion

Existing OMT often suffers from a lack of power when applied with discrete
test statistics, which is a common situation in data sets where A/B testing is
based upon counts. To fill the gap, we introduce new SURE versions of some
existing classical procedures, that “reward” the base procedures by spending
more efficiently the $\alpha$-wealth according to known bounds on the null
cumulative distribution functions. We show that our new SURE procedures
provide rigorous control of online error criteria (FWER or mFDR) under
classical assumptions while offering a systematic power enhancement. When
using discrete Fisher exact test statistics, the improvement is substantial,
both for simulated and real data. All our numerical experiments (simulations
and application) are reproducible from the code provided in the repository
https://github.com/iqm15/SURE_OMT.

While our results address several issues, they also raise some new questions.
First, the bandwidth of the kernel-based SURE spending sequence
$\gamma^{\prime}$ (9) has been chosen in a loose way here, but tuning the
bandwidth is certainly interesting from a power enhancement perspective (see
Appendix B.4). Also, in applications, the user would possibly like to select
the bandwidth in a data dependent fashion without losing control over type I
error rate. These two issues are interesting extensions for future
developments. Second, while our work focuses on marginal FDR, it would be
desirable to build rewarded OMT that control the (non-marginal) FDR. However,
usual proofs rely on a monotonicity property of the critical value sequence
(Ramdas et al.,, 2017) that is difficult to satisfy here, because the super-
uniformity reward naturally varies across time. Hence, deriving rewarded FDR
controlling procedures is a challenging issue that is left for future
investigations. Finally, most of our results rely on an independence
assumption, see (3). While this can be considered as a mild restriction in an
online framework, relaxing it or incorporating a known dependence structure in
OMT is an interesting avenue for future research.

## Acknowledgements

This work has been supported by ANR-16-CE40-0019 (SansSouci), ANR-17-CE40-0001
(BASICS) and by the GDR ISIS through the “projets exploratoires” program
(project TASTY). It is part of project DO 2463/1-1, funded by the Deutsche
Forschungsgemeinschaft. The authors thank Florian Junge for his help regarding
technical issues when running the simulations and Natasha Karp for
explanations on the IMPC data.

## 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.
  * 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, 57(1):289–300.
  * Chen and Arias-Castro, (2021) Chen, S. and Arias-Castro, E. (2021).  On the power of some sequential multiple testing procedures.  Ann. Inst. Stat. Math., 73(2):311–336.
  * Chen and Kasiviswanathan, (2020) Chen, S. and Kasiviswanathan, S. (2020).  Contextual online false discovery rate control.  In Chiappa, S. and Calandra, R., editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 952–961. PMLR.
  * Chen et al., (2018) Chen, X., Doerge, R. W., and Heyse, J. F. (2018).  Multiple testing with discrete data: proportion of true null hypotheses and two adaptive FDR procedures.  Biom. J., 60(4):761–779.
  * Chen et al., (2015) Chen, X., Doerge, R. W., and Sarkar, S. K. (2015).  A weighted FDR procedure under discrete and heterogeneous null distributions.  arXiv e-prints, page arXiv:1502.00973.
  * Dickhaus et al., (2012) Dickhaus, T., Straßburger, K., Schunk, D., Morcillo-Suarez, C., Illig, T., and Navarro, A. (2012).  How to analyze many contingency tables simultaneously in genetic association studies.  Statistical applications in genetics and molecular biology, 11(4).
  * Döhler, (2016) Döhler, S. (2016).  A discrete modification of the Benjamini–-Yekutieli procedure.  Econometrics and Statistics.
  * Durand et al., (2019) Durand, G., Junge, F., Döhler, S., and Roquain, E. (2019).  DiscreteFDR: An R package for controlling the false discovery rate for discrete test statistics.  arXiv e-prints, page arXiv:1904.02054.
  * Döhler et al., (2018) Döhler, S., Durand, G., and Roquain, E. (2018).  New FDR bounds for discrete and heterogeneous tests.  Electronic Journal of Statistics, 12(1):1867 – 1900.
  * 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.
  * Gang et al., (2020) Gang, B., Sun, W., and Wang, W. (2020).  Structure-adaptive sequential testing for online false discovery rate control.
  * (13) Gilbert, P. (2005a).  A modified false discovery rate multiple-comparisons procedure for discrete data, applied to human immunodeficiency virus genetics.  Journal of the Royal Statistical Society. Series C, 54(1):143–158.
  * (14) Gilbert, P. B. (2005b).  A modified false discovery rate multiple-comparisons procedure for discrete data, applied to human immunodeficiency virus genetics.  Journal of the Royal Statistical Society: Series C (Applied Statistics), 54(1):143–158.
  * Habiger, (2015) Habiger, J. D. (2015).  Multiple test functions and adjusted $p$-values for test statistics with discrete distributions.  J. Statist. Plann. Inference, 167:1–13.
  * Heller and Gur, (2011) Heller, R. and Gur, H. (2011).  False discovery rate controlling procedures for discrete tests.  ArXiv e-prints.
  * Heller and Gur, (2011) Heller, R. and Gur, H. (2011).  False discovery rate controlling procedures for discrete tests.
  * Heyse, (2011) Heyse, J. F. (2011).  A false discovery rate procedure for categorical data.  In Recent Advances in Biostatistics: False Discovery Rates, Survival Analysis, and Related Topics, pages 43–58.
  * 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.
  * Johari et al., (2019) Johari, R., Pekelis, L., and Walsh, D. J. (2019).  Always valid inference: Bringing sequential analysis to a/b testing.
  * Johnson et al., (2020) Johnson, K. D., Stine, R. A., and Foster, D. P. (2020).  Fitting high-dimensional interaction models with error control.
  * 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.
  * Katsevich and Ramdas, (2020) Katsevich, E. and Ramdas, A. (2020).  Simultaneous high-probability bounds on the false discovery proportion in structured, regression and online settings.  The Annals of Statistics, 48(6):3465 – 3487.
  * 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, KDD ’13, page 1168?1176, New York, NY, USA. Association for Computing Machinery.
  * Kohavi et al., (2020) Kohavi, R., Tang, D., Xu, Y., Hemkens, L. G., and Ioannidis, J. P. (2020).  Online randomized controlled experiments at scale: lessons and extensions to medicine.  Trials, 21(1):1–9.
  * Lark, (2017) Lark, R. M. (2017).  Controlling the marginal false discovery rate in inferences from a soil dataset with $\alpha$-investment.  European Journal of Soil Science, 68(2):221–234.
  * Li and Barber, (2017) Li, A. and Barber, R. F. (2017).  Accumulation tests for fdr control in ordered hypothesis testing.  Journal of the American Statistical Association, 112(518):837–849.
  * Muñoz-Fuentes et al., (2018) Muñoz-Fuentes, V., Cacheiro, P., Meehan, T. F., Aguilar-Pimentel, J. A., Brown, S. D. M., Flenniken, A. M., Flicek, P., Galli, A., Mashhadi, H. H., Hrabě De Angelis, M., Kim, J. K., Lloyd, K. C. K., McKerlie, C., Morgan, H., Murray, S. A., Nutter, L. M. J., Reilly, P. T., Seavitt, J. R., Seong, J. K., Simon, M., Wardle-Jones, H., Mallon, A.-M., Smedley, D., and Parkinson, H. E. (2018).  The International Mouse Phenotyping Consortium (IMPC): a functional catalogue of the mammalian genome that informs conservation $\times$ the IMPC consortium.  Conservation Genetics, 3(4):995–1005.
  * (29) Ramdas, A., Chen, J., Wainwright, M. J., and Jordan, M. I. (2018a).  Dagger: A sequential algorithm for fdr control on dags.
  * 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.  In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc.
  * (31) Ramdas, A., Zrnic, T., Wainwright, M. J., and Jordan, M. I. (2018b).  SAFFRON: an adaptive algorithm for online control of the false discovery rate.  In Dy, J. G. and Krause, A., editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 4283–4291. PMLR.
  * Tarone, (1990) Tarone, R. E. (1990).  A modified bonferroni method for discrete data.  Biometrics, 46(2):515–522.
  * Tian and Ramdas, (2019) Tian, J. and Ramdas, A. (2019).  ADDIS: an adaptive discarding algorithm for online FDR control with conservative nulls.  In Wallach, H. M., Larochelle, H., Beygelzimer, A., d’Alché-Buc, F., Fox, E. B., and Garnett, R., editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 9383–9391.
  * 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.  PMID: 33413033.
  * Weinstein and Ramdas, (2020) Weinstein, A. and Ramdas, A. (2020).  Online control of the false coverage rate and false sign rate.  In III, H. D. and Singh, A., editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10193–10202. PMLR.
  * Westfall and Wolfinger, (1997) Westfall, P. and Wolfinger, R. (1997).  Multiple tests with discrete distributions.  The American Statistician, 51(1):3–8.
  * Xu and Ramdas, (2021) Xu, Z. and Ramdas, A. (2021).  Dynamic algorithms for online multiple testing.
  * Yang et al., (2017) Yang, F., Ramdas, A., Jamieson, K., and Wainwright, M. J. (2017).  A framework for multi-a(rmed)/b(andit) testing with online fdr control.
  * Zhang et al., (2020) Zhang, W., Kamath, G., and Cummings, R. (2020).  Paprika: Private online false discovery rate control.
  * Zrnic et al., (2020) Zrnic, T., Jiang, D., Ramdas, A., and Jordan, M. (2020).  The power of batching in multiple hypothesis testing.  In Chiappa, S. and Calandra, R., editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, 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–33:39.

##  Appendix A Proofs

###  A.1 Proofs for online FWER control

We start by proving Theorem 3.3 and then deduce Theorems 3.1 and 3.2.

###### Proof of Theorem 3.3.

First, let us show that for any critical values $(\alpha_{t},t\geq 1)$, a
sufficient condition for FWER control under (2) is given by

$\displaystyle\alpha_{T}+\sum_{t=1}^{T-1}{\mathbf{1}\\{p_{t}(X_{t})\geq\lambda\\}}F_{t}(\alpha_{t})\leq(1-\lambda)\alpha\qquad\text{(a.s.)}$
(33)

if either (3) or if $(\alpha_{t},t\geq 1)$ are deterministic for all $T\geq
1$. This comes from Markov’s inequality combined with Lemma A.1:

$\displaystyle\textnormal{FWER}(T,\mathcal{A},P)$
$\displaystyle\leq\mathbf{E}_{X\sim
P}\Big{(}\sum_{t=1}^{T}{\mathbf{1}\\{t\in\mathcal{H}_{0}(P),p_{t}\leq\alpha_{t}\\}}\Big{)}$
$\displaystyle\leq(1-\lambda)^{-1}\>\mathbf{E}\left(\sum_{t=1}^{T}{\mathbf{1}\\{p_{t}(X_{t})\geq\lambda\\}}F_{t}(\alpha_{t})\right)$
$\displaystyle\leq(1-\lambda)^{-1}\>\mathbf{E}\left(\alpha_{T}+\sum_{t=1}^{T-1}{\mathbf{1}\\{p_{t}(X_{t})\geq\lambda\\}}F_{t}(\alpha_{t})\right),$

which gives the announced sufficient condition. Now, we obtain statement (i)
of the theorem by verifying the above criterion (33) for $\alpha^{0}_{t}$
using the (crude) bound $F_{t}(x)\leq x$ and assumption (19). Next, we obtain
statement (ii) of the theorem by verifying the above criterion (33) for
$\alpha_{t}$. This is done by reducing this to a statement on $\alpha^{0}_{t}$
via Lemma A.2. More precisely, with $a_{T}=\sum_{t=1}^{T}\gamma^{\prime}_{t},$
we have

$\displaystyle\alpha_{T}+\sum_{t=1}^{T-1}{\mathbf{1}\\{p_{t}(X_{t})\geq\lambda\\}}F_{t}(\alpha_{t})$
$\displaystyle\leq\alpha_{T}+\sum_{t=1}^{T-1}{\mathbf{1}\\{p_{t}\geq\lambda\\}}\left[(1-a_{T-t})\alpha_{t}+a_{T-t}F_{t}(\alpha_{t})\right]$
$\displaystyle=\alpha^{0}_{T}+\sum_{t=1}^{T-1}{\mathbf{1}\\{p_{t}\geq\lambda\\}}\alpha^{0}_{t}\leq\alpha,$

where the equality above is true provided that the following recursion holds
for all $T\geq 1$,

$\displaystyle\alpha_{T}=\alpha^{0}_{T}+\sum_{t=1}^{T-1}{\mathbf{1}\\{p_{t}\geq\lambda\\}}\alpha^{0}_{t}-\sum_{t=1}^{T-1}{\mathbf{1}\\{p_{t}\geq\lambda\\}}\left[(1-a_{T-t})\alpha_{t}+a_{T-t}F_{t}(\alpha_{t})\right].$

This is true by Lemma A.2 because of the expression (20) of $\alpha_{t}$. This
concludes the proof. ∎

###### Proof of Theorems 3.1 and 3.2.

Theorems 3.1 and 3.2 are corollaries of Theorem 3.3, by considering
$\mathcal{A}^{0}=\mathcal{A}^{\mbox{\tiny OB}}$ ($\lambda=0$) and
$\mathcal{A}^{0}=\mathcal{A}^{\mbox{\tiny AOB}}$, respectively. Indeed,
checking (19) is straightforward for $\mathcal{A}^{\mbox{\tiny OB}}$ from the
spending sequence definition or comes from Lemma A.3 for
$\mathcal{A}^{\mbox{\tiny AOB}}$. ∎

###  A.2 Proofs for online mFDR control

The global proof strategy is similar to the one used for FWER: we start by
proving Theorem 4.3 and then deduce Theorem 4.1 and Theorem 4.2.

###### Proof of Theorem 4.3.

First, we establish that mFDR control is provided under (2) and (3) for any
procedure $\mathcal{A}=(\alpha_{t},t\geq 1)$ if

$\displaystyle\alpha_{T}+\sum_{1\leq t\leq T-1,\atop
p_{t}\geq\lambda}F_{t}(\alpha_{t})\leq(1-\lambda)\alpha\>(1\vee
R(T)),\quad\mbox{(a.s.)}.$ (34)

Indeed, by Lemma A.1, we have

$\displaystyle\mathbf{E}_{X\sim
P}\Big{(}\sum_{t=1}^{T}{\mathbf{1}\\{t\in\mathcal{H}_{0},p_{t}\leq\alpha_{t}\\}}\Big{)}$
$\displaystyle\leq(1-\lambda)^{-1}\>\mathbf{E}\left(\sum_{t=1}^{T}{\mathbf{1}\\{p_{t}(X_{t})\geq\lambda\\}}F_{t}(\alpha_{t})\right)$
$\displaystyle\leq\alpha\>\mathbf{E}(1\vee R(T)),$

by using (34), which is exactly the desired mFDR control. Now, statement (i)
holds because (34) holds for $(\alpha^{0}_{t},t\geq 1)$ from (32) and (2).
Finally, we establish statement (ii). By (32) and (2), condition (34) holds
for $(\alpha_{t},t\geq 1)$ if for all $T\geq 1$,

$\displaystyle\alpha_{T}+\sum_{t=1}^{T-1}{\mathbf{1}\\{p_{t}(X_{t})\geq\lambda\\}}\left[(1-a_{T-t})\alpha_{t}+a_{T-t}F_{t}(\alpha_{t})\right]=\alpha^{0}_{T}+\sum_{p_{t}\geq\lambda,1\leq
t\leq T-1}\alpha^{0}_{t},$

where $a_{T}=\sum_{t=1}^{T}\gamma^{\prime}_{t}$. Now the last display holds
true by Lemma A.2 because of (20), which concludes the proof. ∎

###### Proof of Theorems 4.1 and 4.2.

Theorem 4.1 and Theorem 4.2 can be derived from Theorem 4.3 for
$\mathcal{A}^{0}=\mathcal{A}^{\mbox{\tiny LORD}}$ (using $\lambda=0$) and
$\mathcal{A}^{0}=\mathcal{A}^{\mbox{\tiny ALORD}}$, respectively, by checking
(32) in both cases. First, for $\mathcal{A}^{\mbox{\tiny LORD}}$, we have

$\displaystyle\sum_{t=1}^{T}\alpha^{\mbox{\tiny LORD}}_{t}$
$\displaystyle=\sum_{t=1}^{T}\left(W_{0}\gamma_{t}+(\alpha-
W_{0})\gamma_{t-\tau_{1}}+\alpha\sum_{j\geq 2}\gamma_{t-\tau_{j}}\right)$
$\displaystyle=W_{0}\sum_{t=1}^{T}\gamma_{t}+(\alpha-
W_{0})\sum_{t=1}^{T}\gamma_{t-\tau_{1}}+\alpha\sum_{j\geq
2}{\mathbf{1}\\{T-\tau_{j}\geq 1\\}}\sum_{t=1}^{T}\gamma_{t-\tau_{j}}$
$\displaystyle\leq\alpha(1+0\vee(R(T-1)-1))\leq\alpha(1\vee R(T)),$ (35)

because $\tau_{j}\leq T-1$ is equivalent to $R(T-1)\geq j$ by definition.
Second, for $\mathcal{A}^{\mbox{\tiny ALORD}}$, we proceed similarly with the
help of Lemma A.3: by definition (30), we have

$\displaystyle(1-\lambda)^{-1}\left(\alpha^{\mbox{\tiny
ALORD}}_{T}+\sum_{1\leq t\leq T-1,\atop p_{t}\geq\lambda}\alpha^{\mbox{\tiny
ALORD}}_{t}\right)$
$\displaystyle=W_{0}\left(\gamma_{\mathcal{T}_{0}(T)}+\sum_{1\leq t\leq
T-1,\atop p_{t}\geq\lambda}\gamma_{\mathcal{T}_{0}(t)}\right)+(\alpha-
W_{0})\left(\gamma_{\mathcal{T}_{1}(T)}+\sum_{1\leq t\leq T-1,\atop
p_{t}\geq\lambda}\gamma_{\mathcal{T}_{1}(t)}\right)$
$\displaystyle\>\>\>+\alpha\sum_{j\geq
2}{\mathbf{1}\\{T\geq\tau_{j}+1\\}}\left(\gamma_{\mathcal{T}_{j}(T)}+\sum_{1\leq
t\leq T-1,\atop p_{t}\geq\lambda}\gamma_{\mathcal{T}_{j}(t)}\right).$

Finally, by using (38) and (39), the latter is equal to

$\displaystyle W_{0}\sum_{t=1}^{\mathcal{T}_{0}(T)}\gamma_{t}+(\alpha-
W_{0})\sum_{t=1}^{\mathcal{T}_{1}(T)}\gamma_{t}+\alpha\sum_{j\geq
2}{\mathbf{1}\\{T\geq\tau_{j}+1\\}}\sum_{t=1}^{\mathcal{T}_{j}(T)}\gamma_{t}$
$\displaystyle\leq W_{0}+\alpha-W_{0}+\alpha\sum_{j\geq
2}{\mathbf{1}\\{T\geq\tau_{j}+1\\}}=\alpha(1+0\vee(R(T-1)-1))\leq\alpha\>(1\vee
R(T)),$

because $T\geq\tau_{j}+1$ if and only if $R(T-1)\geq j$. ∎

###  A.3 Auxiliary lemmas

The following lemma provides a tool for controlling both online FWER and mFDR.

######  Lemma A.1.

For any procedure $\mathcal{A}=(\alpha_{t},t\geq 1)$, we have for all
$\lambda\in[0,1)$,

$\displaystyle\mathbf{E}_{X\sim
P}\Big{(}\sum_{t=1}^{T}{\mathbf{1}\\{t\in\mathcal{H}_{0},p_{t}\leq\alpha_{t}\\}}\Big{)}\leq(1-\lambda)^{-1}\>\mathbf{E}\left(\sum_{t=1}^{T}{\mathbf{1}\\{p_{t}(X_{t})\geq\lambda\\}}F_{t}(\alpha_{t})\right),$
(36)

provided that (2) holds and if either (3) holds or if the critical values
$(\alpha_{t},t\geq 1)$ are deterministic.

###### Proof.

Recall $\alpha_{t}$ is either deterministic or $X_{1:(t-1)}$-measurable (in
which case it is independent of $p_{t}(X_{t})$ under (3)). Therefore, under
the conditions of the lemma, we have in any case: for all
$t\in\mathcal{H}_{0}$, both

$\displaystyle\mathbf{E}\left(\frac{{\mathbf{1}\\{p_{t}(X_{t})>\lambda\\}}}{1-\lambda}\bigg{|}\alpha_{t}\right)\geq
1,\>\>\>\mathbf{P}\left(p_{t}(X_{t})\leq\alpha_{t}\>|\>\alpha_{t}\right)\leq
F_{t}(\alpha_{t}).$

This entails

$\displaystyle\mathbf{E}_{X\sim
P}\Big{(}\sum_{t=1}^{T}{\mathbf{1}\\{t\in\mathcal{H}_{0},p_{t}\leq\alpha_{t}\\}}\Big{)}$
$\displaystyle=\sum_{t=1}^{T}{\mathbf{1}\\{t\in\mathcal{H}_{0}\\}}\>\mathbf{E}\left(\mathbf{P}(p_{t}(X_{t})\leq\alpha_{t}\>|\>\alpha_{t})\right)$
$\displaystyle\leq\sum_{t=1}^{T}{\mathbf{1}\\{t\in\mathcal{H}_{0}\\}}\>\mathbf{E}\left(F_{t}(\alpha_{t})\right)$
$\displaystyle\leq\sum_{t=1}^{T}{\mathbf{1}\\{t\in\mathcal{H}_{0}\\}}\>\mathbf{E}\left(F_{t}(\alpha_{t})\mathbf{E}\left(\frac{{\mathbf{1}\\{p_{t}(X_{t})\geq\lambda\\}}}{1-\lambda}\>|\>\alpha_{t}\right)\right)$
$\displaystyle\leq(1-\lambda)^{-1}\>\mathbf{E}\left(\sum_{t=1}^{T}{\mathbf{1}\\{p_{t}(X_{t})\geq\lambda\\}}F_{t}(\alpha_{t})\right).$

∎

The following representation lemma is the key tool for building the new
rewarded critical values.

######  Lemma A.2.

Let $(\alpha^{0}_{t},t\geq 1)$ be any nonnegative sequence. Let
$(\tilde{\alpha}_{t},t\geq 1)$ be the sequence defined by the recursive
relation

$\tilde{\alpha}_{T}=\alpha^{0}_{T}+\sum_{t=1}^{T-1}{\mathbf{1}\\{p_{t}\geq\lambda\\}}\alpha^{0}_{t}-\sum_{t=1}^{T-1}{\mathbf{1}\\{p_{t}\geq\lambda\\}}\left[(1-a_{T-t})\tilde{\alpha}_{t}+a_{T-t}F_{t}(\tilde{\alpha}_{t})\right],\>\>\quad
T\geq 1,$ (37)

where $a_{T}=\sum_{t=1}^{T}\gamma^{\prime}_{t},$ $T\geq 1$ for any real values
$\gamma^{\prime}_{t}$, $p_{t}$, $\lambda$ and functions $F_{t}$. Let
$(\bar{\alpha}_{t},t\geq 1)$ be the sequence defined by the recursive relation

$\displaystyle\bar{\alpha}_{T}=\alpha^{0}_{T}+\sum_{1\leq t\leq T-1\atop
p_{t}\geq\lambda}\gamma^{\prime}_{T-t}(\bar{\alpha}_{t}-F_{t}(\bar{\alpha}_{t}))+{\mathbf{1}\\{p_{T-1}<\lambda\\}}(\bar{\alpha}_{T-1}-\alpha^{0}_{T-1}),\quad
T\geq 1.$

Then we have $\tilde{\alpha}_{t}=\bar{\alpha}_{t}$ for all $t\geq 1$.
Moreover, $\bar{\alpha}_{t}\geq\bar{\alpha}^{0}_{t}$ for all $t\geq 1$ under
(2). In particular, these critical values are nonnegative.

###### Proof.

Clearly, $\tilde{\alpha}_{1}=\alpha^{0}_{1}=\bar{\alpha}_{1}$ so the result is
satisfied for $T=1$. For $T\geq 2$, by using (37) for $\tilde{\alpha}_{T}$ and
$\tilde{\alpha}_{T-1}$, we have

$\displaystyle\tilde{\alpha}_{T}-\tilde{\alpha}_{T-1}=$
$\displaystyle\>\alpha^{0}_{T}-\alpha^{0}_{T-1}+{\mathbf{1}\\{p_{T-1}\geq\lambda\\}}\alpha^{0}_{T-1}$
$\displaystyle-{\mathbf{1}\\{p_{T-1}\geq\lambda\\}}\left[(1-a_{1})\tilde{\alpha}_{T-1}+a_{1}F_{T-1}(\tilde{\alpha}_{T-1})\right]$
$\displaystyle+\sum_{t=1}^{T-2}{\mathbf{1}\\{p_{t}\geq\lambda\\}}\left[(a_{T-t}-a_{T-t-1})\tilde{\alpha}_{t}-(a_{T-t}-a_{T-t-1})F_{t}(\tilde{\alpha}_{t})\right].$

Hence, by using
$\tilde{\alpha}_{T-1}=\tilde{\alpha}_{T-1}{\mathbf{1}\\{p_{T-1}<\lambda\\}}+\tilde{\alpha}_{T-1}{\mathbf{1}\\{p_{T-1}\geq\lambda\\}}$,
we obtain

$\displaystyle\tilde{\alpha}_{T}=$
$\displaystyle\>\alpha^{0}_{T}-{\mathbf{1}\\{p_{T-1}<\lambda\\}}\alpha^{0}_{T-1}+\tilde{\alpha}_{T-1}{\mathbf{1}\\{p_{T-1}<\lambda\\}}$
$\displaystyle+{\mathbf{1}\\{p_{T-1}\geq\lambda\\}}\left[\gamma^{\prime}_{1}\tilde{\alpha}_{T-1}-\gamma^{\prime}_{1}F_{T-1}(\tilde{\alpha}_{T-1})\right]$
$\displaystyle+\sum_{t=1}^{T-2}{\mathbf{1}\\{p_{t}\geq\lambda\\}}\left[\gamma^{\prime}_{T-t}\tilde{\alpha}_{t}-\gamma^{\prime}_{T-t}F_{t}(\tilde{\alpha}_{t})\right],$

because $\gamma^{\prime}_{1}=a_{1}$, and we recognize the expression given in
the lemma.

Let us finally prove that $\bar{\alpha}_{T}\geq\bar{\alpha}^{0}_{T}$ for all
$T\geq 1$. This is true for $\bar{\alpha}_{1}$ because
$\bar{\alpha}_{1}=\alpha^{0}_{1}$. Now, if
$\bar{\alpha}_{1}\geq\alpha^{0}_{1},\dots,\bar{\alpha}_{T-1}\geq\alpha^{0}_{T-1}$
then we also have

$\bar{\alpha}_{T}=\alpha^{0}_{T}+\sum_{1\leq t\leq T-1\atop
p_{t}\geq\lambda}\gamma^{\prime}_{T-t}(\bar{\alpha}_{t}-F_{t}(\bar{\alpha}_{t}))+{\mathbf{1}\\{p_{T-1}<\lambda\\}}(\bar{\alpha}_{T-1}-\alpha^{0}_{T-1})\geq\alpha^{0}_{T},$

because $\bar{\alpha}_{t}\geq F_{t}(\bar{\alpha}_{t})$ by (2). This finishes
the proof. ∎

We now establish a result for the functionals $\mathcal{T}(\cdot)$ and
$\mathcal{T}_{j}(\cdot)$, $j\geq 1$, which are used by the adaptive procedures
$\mathcal{A}^{\mbox{\tiny AOB}}$ and $\mathcal{A}^{\mbox{\tiny ALORD}}$,
respectively.

######  Lemma A.3.

Consider the functional $\mathcal{T}(\cdot)$ defined by (16) for some
realization of the $p$-values and some $\lambda\in[0,1)$. Then for any
sequence $(\gamma_{t})_{t\geq 1}$ and for any $T\geq 1$, we have

$\displaystyle\sum_{t=1}^{T}{\mathbf{1}\\{p_{t}\geq\lambda\\}}\gamma_{\mathcal{T}(t)}=\sum_{t=1}^{\mathcal{T}(T+1)-1}\gamma_{t}.$
(38)

In addition, for any $j\geq 1$, consider the $\tau_{j}$ defined by (22) and
the functional $\mathcal{T}_{j}(\cdot)$ defined by (28). Then for all
$T\geq\tau_{j}+1$,

$\sum_{1\leq t\leq T\atop
p_{t}\geq\lambda}\gamma_{\mathcal{T}_{j}(t)}=\sum_{t=1}^{\mathcal{T}_{j}(T+1)-1}\gamma_{t}.$
(39)

###### Proof.

Let us first prove (38). Since $\mathcal{T}(t+1)=\mathcal{T}(t)+1$ when
$p_{t}\geq\lambda$ from definition (16), we can write

$\displaystyle\sum_{t=1}^{T}{\mathbf{1}\\{p_{t}\geq\lambda\\}}\gamma_{\mathcal{T}(t)}=\sum_{t=1}^{T}{\mathbf{1}\\{p_{t}\geq\lambda\\}}\gamma_{\mathcal{T}(t+1)-1}=\sum_{t=2}^{T+1}{\mathbf{1}\\{p_{t-1}\geq\lambda\\}}\gamma_{\mathcal{T}(t)-1}.$

Additionally, it is clear that $\mathcal{T}(\cdot)$ is a bijection mapping
$\\{1,\,2\leq t\leq T+1\>:p_{t-1}\geq\lambda\\}$ into
$\\{1,2,\dots,\mathcal{T}(T+1)\\}$. Hence, the latter sum can be rewritten as
$\sum_{t=2}^{\mathcal{T}(T+1)}\gamma_{t-1}=\sum_{t=1}^{\mathcal{T}(T+1)-1}\gamma_{t}$
which provides (38).

Second, for proving (39), the crucial point is that according to the
definition of $\mathcal{T}_{j}(T)$ (28), the functional
$\mathcal{T}_{j}:\\{\tau_{j}+1,\dots\\}\to\\{1,\dots\\}$ is a bijection from
$\\{\tau_{j}+1\\}\cup\\{t\in\\{\tau_{j}+2,\dots,T+1\\}\>:\>p_{t-1}\geq\lambda\\}$
to $\\{1,\dots,\mathcal{T}_{j}(T+1)\\}$, for any $j\geq 1$ and
$T\geq\tau_{j}+1$. In particular, this entails

$\displaystyle\sum_{p_{t}\geq\lambda,1\leq t\leq
T}\gamma_{\mathcal{T}_{j}(t)}$
$\displaystyle=\sum_{p_{t}\geq\lambda,\tau_{j}+1\leq t\leq
T}\gamma_{\mathcal{T}_{j}(t)}=\sum_{p_{t}\geq\lambda,\tau_{j}+1\leq t\leq
T}\gamma_{\mathcal{T}_{j}(t+1)-1}$
$\displaystyle=\sum_{p_{t-1}\geq\lambda,\tau_{j}+2\leq t\leq
T+1}\gamma_{\mathcal{T}_{j}(t)-1}=\sum_{t=2}^{\mathcal{T}_{j}(T+1)}\gamma_{t-1}=\sum_{t=1}^{\mathcal{T}_{j}(T+1)-1}\gamma_{t}$

This proves (39). ∎

##  Appendix B Additional numerical experiments

###  B.1 Sample size

Figure 10 illustrates results when the sample size $N$, i.e. the subjects
number per group, takes values in the set $\\{25,50,\ldots,150\\}$. As
expected, the power plots show that the detection problem becomes easier when
$N$ increases. As the $p$-value distributions become less discrete for
sufficiently large $N$, all the procedures behave similarly for these values
of $N$, and their performance improves. We see that our rewarded procedures do
well on the whole range of $N$ values and improve substantially on existing
OMT for small and moderate values of $N$, including our default value $N=25$.

|
---|---
Figure 10: Power and type I error rates of the considered procedures versus
$N\in\\{25,50,\ldots,150\\}$, the number of subjects in the groups.

###  B.2 Signal strength

Here, we vary the strength of the signal $p_{3}$ in the set
$\\{0.1,0.2,\ldots,1\\}$. We see that the SURE procedures dominate their base
counterparts, as expected. In addition, depending on the signal strength, the
gain in power can be considerable. Also note that, perhaps surprisingly, all
curves exhibit a decrease in power for $p_{3}$ near $1$. Since this happens
even for the original OB procedure, this is not due to the super-uniformity
reward, but could perhaps be caused by the behavior of the power function of
multiple Fisher exact tests taken at different levels.

|
---|---
Figure 11: Power and type I error rates of the considered procedures versus
the strength of the signal $p_{3}\in\\{0.1,0.2,\ldots,0.9,1\\}$.

###  B.3 Adaptivity parameter

We study the choice of $\lambda$ for the procedures using adaptivity. It seems
like $\lambda=0.5$ is a reasonable choice for the adaptive procedures.

|
---|---
Figure 12: Power and type I error rates, for the considered procedures, versus
the adaptivity parameter $\lambda$.

###  B.4 Rectangular kernel bandwidth

Finally, we study the choice of the bandwidth parameter for the rectangular
kernel used for the rewarded procedures. As we can see, using a smaller
bandwidth provides the best performance for the mFDR controlling rewarded
procedures, whereas FWER controlling procedures require a larger bandwidth.
The choices $h=100$ for FWER controlling procedures, and $h=10$ for mFDR
controlling procedures seem reasonable although not necessarily optimal.

|
---|---
Figure 13: Power for FWER (left) and mFDR (right) rewarded procedures versus
the proportion of signal $\pi_{A}$, for different kernel bandwidths.

##  Appendix C Additional figures for the analysis of IMPC data

###  C.1 Localization of small $p$-values

Figures 14 and 15 show that small $p$-values mostly occur at the beginning of
the data set, both for male and female mice.

---
Figure 14: $p$-values for male mice in the IMPC data of Section 6. The left
panel presents all $p$-values, the right panel the first 3000 $p$-values. The
$p$-values have been transformed as in Figure 3.
---
Figure 15: $p$-values for female mice in the IMPC data of Section 6. The left
panel presents all $p$-values, the right panel the first 3000 $p$-values. The
$p$-values have been transformed as in Figure 3.

###  C.2 Figures for female mice in the IMPC data

Figures 16 and 17 display the critical values of the studied online procedures
when applied to the IMPC data in the case of female mice.

|
---|---
Figure 16: Same as Figure 8 but for female mice of IMPC data (see Section 6).  |
---|---
Figure 17: Same as Figure 9 for female mice of IMPC data (see Section 6).