Online Rules for Control of False Discovery Rate and False Discovery
  Exceedance
  Multiple hypothesis testing is a core problem in statistical inference and
arises in almost every scientific field. Given a set of null hypotheses
$\mathcal{H}(n) = (H_1,\dotsc, H_n)$, Benjamini and Hochberg introduced the
false discovery rate (FDR), which is the expected proportion of false positives
among rejected null hypotheses, and proposed a testing procedure that controls
FDR below a pre-assigned significance level. Nowadays FDR is the criterion of
choice for large scale multiple hypothesis testing. In this paper we consider
the problem of controlling FDR in an "online manner". Concretely, we consider
an ordered --possibly infinite-- sequence of null hypotheses $\mathcal{H} =
(H_1,H_2,H_3,\dots )$ where, at each step $i$, the statistician must decide
whether to reject hypothesis $H_i$ having access only to the previous
decisions. This model was introduced by Foster and Stine. We study a class of
"generalized alpha-investing" procedures and prove that any rule in this class
controls online FDR, provided $p$-values corresponding to true nulls are
independent from the other $p$-values. (Earlier work only established mFDR
control.) Next, we obtain conditions under which generalized alpha-investing
controls FDR in the presence of general $p$-values dependencies. Finally, we
develop a modified set of procedures that also allow to control the false
discovery exceedance (the tail of the proportion of false discoveries).
Numerical simulations and analytical results indicate that online procedures do
not incur a large loss in statistical power with respect to offline approaches,
such as Benjamini-Hochberg.
